শুক্রবার, ২৭ অক্টোবর, ২০১৭

UVA 10653 - Bombs! NO they are Mines!!

#include<bits/stdc++.h>
using namespace std;
long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
char s[1010][1010];
long dis[1010][1010]={0},vis[1010][1010]={0};
long bfs(long x,long y)
{
    queue< pair<long,long> >q;
    pair<long,long>pr;
    long x1,y1,i1;
    dis[x][y]=0;
    vis[x][y]=1;
    q.push(make_pair(x,y));
    while(!q.empty())
    {
        pr=q.front();
        x1=pr.first;
        y1=pr.second;
        for(i1=0;i1<4;i1++)
        {
            x1=pr.first+dx[i1];
            y1=pr.second+dy[i1];
            if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='#'))
            {
                dis[x1][y1]=dis[pr.first][pr.second]+1;
                q.push(make_pair(x1,y1));
                vis[x1][y1]=1;
                if(s[x1][y1]=='h')
                {
                    return dis[x1][y1];
                }
            }
        }
        q.pop();
    }
}
int main()
{
    while(cin>>row>>col)
    {
        if(row==0&&col==0)
            break;
        long n,i,j,rnumbr,pos,a;
        cin>>n;
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                s[i][j]='*';
                dis[i][j]=0;
                vis[i][j]=0;
            }
        }
        for(i=1;i<=n;i++)
        {
            cin>>rnumbr;
            cin>>a;
            for(j=1;j<=a;j++)
            {
                cin>>pos;
                s[rnumbr][pos]='#';
            }
        }
        long sx,sy,ddx,ddy;
        cin>>sx>>sy>>ddx>>ddy;
        s[ddx][ddy]='h';
        cout<<bfs(sx,sy)<<endl;
    }
    return 0;
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...