Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int fx[]={1,-1,0,0};
- int fy[]={0,0,1,-1};
- int cell[1005][1005];
- int d[1005][1005];
- bool vis[1005][1005];
- int row,col;
- void mybfs(int sx,int sy)
- {
- //memset(vis,false,sizeof vis);
- vis[sx][sy]=true;
- pair<int, int>p,p1;
- queue<pair<int, int> >q;
- p1=make_pair(sx,sy);
- q.push(p1);
- d[sx][sy]=0;
- while(!q.empty())
- {
- p=q.front();
- q.pop();
- //int ucost=d[p.first][p.second];
- for(int i=0;i<4;i++)
- {
- int tx=p.first+fx[i];
- int ty=p.second+fy[i];
- if(tx>=0 && tx<row && (ty>=0) && ty<col)
- {
- if((cell[tx][ty]!=-1) && (vis[tx][ty]==false))
- {
- d[tx][ty]=d[p.first][p.second]+1;
- vis[tx][ty]=true;
- p=make_pair(tx,ty);
- q.push(p);
- //cout<<tx<<" "<<ty<<" "<<d[tx][ty]<<endl;
- }
- }
- }
- }
- }
- int main()
- {
- while(scanf("%d %d",&row,&col)==2)
- {
- for(int i=0;i<1005;i++)
- for(int j=0;j<1005;j++)
- {
- cell[i][j]=0;
- vis[i][j]=false;
- d[i][j]=0;
- }
- if(row==0 && col==0)
- {
- break;
- }
- int n;
- scanf("%d",&n);
- int r,num,c;
- for(int i=0;i<n;i++)
- {
- scanf("%d %d",&r,&num);
- for(int j=0;j<num;j++)
- {
- cin>>c;
- //vis[r][c]=true;
- cell[r][c]=-1;
- }
- }
- int x1,y1,x2,y2;
- cin>>x1>>y1;
- cin>>x2>>y2;
- mybfs(x1,y1);
- int ans=d[x2][y2];
- cout<<ans<<endl;
- for(int i=0;i<1005;i++)
- for(int j=0;j<1005;j++)
- {
- cell[i][j]=0;
- vis[i][j]=false;
- d[i][j]=0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment