Maruf_Hasan

uva 10653

Jan 26th, 2019
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int fx[]={1,-1,0,0};
  5. int fy[]={0,0,1,-1};
  6. int cell[1005][1005];
  7. int d[1005][1005];
  8. bool vis[1005][1005];
  9. int row,col;
  10.  
  11. void mybfs(int sx,int sy)
  12. {
  13. //memset(vis,false,sizeof vis);
  14.  
  15. vis[sx][sy]=true;
  16. pair<int, int>p,p1;
  17. queue<pair<int, int> >q;
  18. p1=make_pair(sx,sy);
  19. q.push(p1);
  20. d[sx][sy]=0;
  21. while(!q.empty())
  22. {
  23.  
  24. p=q.front();
  25. q.pop();
  26. //int ucost=d[p.first][p.second];
  27. for(int i=0;i<4;i++)
  28. {
  29. int tx=p.first+fx[i];
  30. int ty=p.second+fy[i];
  31. if(tx>=0 && tx<row && (ty>=0) && ty<col)
  32. {
  33.  
  34. if((cell[tx][ty]!=-1) && (vis[tx][ty]==false))
  35. {
  36. d[tx][ty]=d[p.first][p.second]+1;
  37. vis[tx][ty]=true;
  38. p=make_pair(tx,ty);
  39. q.push(p);
  40. //cout<<tx<<" "<<ty<<" "<<d[tx][ty]<<endl;
  41. }
  42. }
  43. }
  44. }
  45. }
  46.  
  47.  
  48.  
  49.  
  50. int main()
  51. {
  52. while(scanf("%d %d",&row,&col)==2)
  53. {
  54. for(int i=0;i<1005;i++)
  55. for(int j=0;j<1005;j++)
  56. {
  57. cell[i][j]=0;
  58. vis[i][j]=false;
  59. d[i][j]=0;
  60. }
  61.  
  62.  
  63. if(row==0 && col==0)
  64. {
  65. break;
  66. }
  67. int n;
  68. scanf("%d",&n);
  69. int r,num,c;
  70. for(int i=0;i<n;i++)
  71. {
  72. scanf("%d %d",&r,&num);
  73. for(int j=0;j<num;j++)
  74. {
  75. cin>>c;
  76. //vis[r][c]=true;
  77. cell[r][c]=-1;
  78. }
  79. }
  80. int x1,y1,x2,y2;
  81. cin>>x1>>y1;
  82. cin>>x2>>y2;
  83. mybfs(x1,y1);
  84.  
  85. int ans=d[x2][y2];
  86. cout<<ans<<endl;
  87. for(int i=0;i<1005;i++)
  88. for(int j=0;j<1005;j++)
  89. {
  90. cell[i][j]=0;
  91. vis[i][j]=false;
  92. d[i][j]=0;
  93. }
  94.  
  95. }
  96.  
  97. return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment