Thursday, 18 February 2016

UVa 10653 - Bombs! NO they are Mines!!

#include<bits/stdc++.h>
using namespace std;
int graph[1009][1009];
int visited[1009][1009];
int level[1009][1009];
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int main()
{
    while(1)
    {
        int r,c;
        cin>>r>>c;
        if(r==0&&c==0)
            break;
        int row_num;
        cin>>row_num;
        memset(graph,0,sizeof(graph));
        int row,i,j,k;
        for(i=0;i<row_num;i++)
        {
            cin>>row>>k;
            for(j=0;j<k;j++)
            {
                int col;
                cin>>col;
                graph[row][col]=1;
                //cout<<"ROW:"<<row<<" COL:"<<col<<endl;
            }
        }
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        int stx,sty,enx,eny;
        cin>>stx>>sty;
        cin>>enx>>eny;
        visited[stx][sty]=true;
        level[stx][sty]=0;
        q.push(stx);
        q.push(sty);
        int ans;
        while(!q.empty())
        {
            int f1,f2;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            for(int in=0;in<4;in++)
            {
                int v1,v2;
                v1=f1+x[in];
                v2=f2+y[in];
                //cout<<111111111111<<endl;
                if(!visited[v1][v2]&&!level[v1][v2])
                {
                    if(v1>=0&&v1<=r&&v2>=0&&v2<=c&&graph[v1][v2]==0)
                    {
                        level[v1][v2]=level[f1][f2]+1;
                        //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                        q.push(v1);
                        q.push(v2);
                        visited[v1][v2]=true;
                        if(v1==enx&&v2==eny)
                            ans=level[v1][v2];
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

No comments:

Post a Comment