Advertisement
Guest User

Untitled

a guest
May 22nd, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int visited[1010][1010];
  5. int level[1010][1010];
  6. int row[4]= {0,-1,0,1};
  7. int col[4]= {1,0,-1,0};
  8. struct TwoD
  9. {
  10. int r;
  11. int c;
  12. };
  13. int bfs(TwoD s, TwoD e,int r,int c)
  14. {
  15. queue<TwoD>Q;
  16. Q.push(s);
  17. visited[s.r][s.c]=1;
  18. level[s.r][s.c]=0;
  19. while(!Q.empty())
  20. {
  21. if(visited[e.r][e.c]==1)
  22. return level[e.r][e.c];
  23. TwoD u;
  24. u=Q.front();
  25. Q.pop();
  26. for(int i=0; i<4; i++)
  27. {
  28. TwoD p;
  29. p.r=u.r+row[i];
  30. p.c=u.c+col[i];
  31. if(p.r>=0 and p.r<r and p.c>=0 and p.c<c)
  32. if(visited[u.r+row[i]][u.c+col[i]]==0)
  33. {
  34. visited[u.r+row[i]][u.c+col[i]]=1;
  35. level[u.r+row[i]][u.c+col[i]]=level[u.r][u.c]+1;
  36. Q.push(p);
  37. }
  38. }
  39. }
  40. return 0;
  41.  
  42.  
  43. }
  44. int main()
  45. {
  46. int r, c;
  47. while((cin>>r>>c) and r and c)
  48. {
  49. memset(visited, 0, sizeof(visited[0][0]) * 1010 * 1010);
  50. memset(level, 0, sizeof(level[0][0]) * 1010* 1010);
  51. int rows;
  52. cin>>rows;
  53. while(rows--)
  54. {
  55. int rnum;
  56. cin>>rnum;
  57. int bnum;
  58. cin>>bnum;
  59. while(bnum--)
  60. {
  61. int cnum;
  62. cin>>cnum;
  63. visited[rnum][cnum]=1;
  64. }
  65.  
  66. }
  67. TwoD spair,epair;
  68. cin>>spair.r>>spair.c;
  69. cin>>epair.r>>epair.c;
  70. int steps=bfs(spair, epair, r, c);
  71. cout<<steps<<endl;
  72. }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement