Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int visited[1010][1010];
- int level[1010][1010];
- int row[4]= {0,-1,0,1};
- int col[4]= {1,0,-1,0};
- struct TwoD
- {
- int r;
- int c;
- };
- int bfs(TwoD s, TwoD e,int r,int c)
- {
- queue<TwoD>Q;
- Q.push(s);
- visited[s.r][s.c]=1;
- level[s.r][s.c]=0;
- while(!Q.empty())
- {
- if(visited[e.r][e.c]==1)
- return level[e.r][e.c];
- TwoD u;
- u=Q.front();
- Q.pop();
- for(int i=0; i<4; i++)
- {
- TwoD p;
- p.r=u.r+row[i];
- p.c=u.c+col[i];
- if(p.r>=0 and p.r<r and p.c>=0 and p.c<c)
- if(visited[u.r+row[i]][u.c+col[i]]==0)
- {
- visited[u.r+row[i]][u.c+col[i]]=1;
- level[u.r+row[i]][u.c+col[i]]=level[u.r][u.c]+1;
- Q.push(p);
- }
- }
- }
- return 0;
- }
- int main()
- {
- int r, c;
- while((cin>>r>>c) and r and c)
- {
- memset(visited, 0, sizeof(visited[0][0]) * 1010 * 1010);
- memset(level, 0, sizeof(level[0][0]) * 1010* 1010);
- int rows;
- cin>>rows;
- while(rows--)
- {
- int rnum;
- cin>>rnum;
- int bnum;
- cin>>bnum;
- while(bnum--)
- {
- int cnum;
- cin>>cnum;
- visited[rnum][cnum]=1;
- }
- }
- TwoD spair,epair;
- cin>>spair.r>>spair.c;
- cin>>epair.r>>epair.c;
- int steps=bfs(spair, epair, r, c);
- cout<<steps<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement