Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. int m[1001][1001],t[1001][1001],vis[1001][1001];
  5. int c,d;
  6. int dx[4]= {-1,0,0,1};
  7. int dy[4]= {0,-1,1,0};
  8. void bfs(int sx,int sy)
  9. {
  10. int ux,uy,vx,vy;
  11. queue<int>q;
  12. q.push(sx);
  13. q.push(sy);
  14. vis[sx][sy]=1;
  15. while(!q.empty())
  16. {
  17. ux=q.front();
  18. q.pop();
  19. uy=q.front();
  20. q.pop();
  21. for(int k=0; k<4; k++)
  22. {
  23. vx=ux+dx[k];
  24. vy=uy+dy[k];
  25.  
  26. if((vx>=0)&&(vx<=c)&&(vy>=0)&&(vy<=d)&&(!m[vx][vy])&&(!vis[vx][vy]))
  27. {
  28. q.push(vx);
  29. q.push(vy);
  30. vis[vx][vy]=1;
  31. t[vx][vy]=t[ux][uy]+1;
  32. }
  33. }
  34. }
  35. }
  36. int main()
  37. {
  38. int e,row,mine,nom,sx,sy,ex,ey,ga,gb;
  39. cin>>c>>d>>e;
  40. while(e--)
  41. {
  42. cin>>row>>nom;
  43. for(int i=1; i<=nom; i++)
  44. {
  45. cin>>mine;
  46. m[row][mine]=1;
  47. }
  48. }
  49.  
  50. cin>>sx>>sy;
  51. bfs(sx,sy);
  52. cin>>ex>>ey;
  53. cin>>ga>>gb;
  54. cout<<t[ex][ey]<<endl;
  55. /*for(int i=0; i<c; i++)
  56. {
  57. for(int j=0; j<d; j++)
  58. {
  59. cout<<vis[i][j]<<" ";
  60. }
  61. cout<<endl;
  62. }*/
  63.  
  64.  
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement