Advertisement
Guest User

Untitled

a guest
Jul 24th, 2016
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define pii pair<int,int>
  6. #define SET(n) memset(n,-1,sizeof(n))
  7. #define CLR(n) memset(n,0,sizeof(n))
  8. #define MAX 1010
  9.  
  10. int stx,sty,r,c;
  11.  
  12. int fx[]= {1,-1,0,0};
  13. int fy[]= {0,0,1,-1};
  14. int gr[MAX-5][MAX-5];
  15. int d[MAX-5][MAX-5];
  16. int vis[MAX-5][MAX-5];
  17. char s[MAX-5][MAX-5];
  18. bool isvalid(int tx,int ty)
  19. {
  20. if(gr[tx][ty]==INT_MAX) return false;
  21. if(tx>=0 && tx<r && ty>=0 && ty<c && gr[tx][ty]!=-1) return true;
  22. return false;
  23. }
  24.  
  25. void bfsIn2D(int sx,int sy)
  26. {
  27. CLR(vis);
  28. vis[sx][sy]=1;
  29. queue<pii>q;
  30. q.push(make_pair(sx,sy));
  31. while(!q.empty())
  32. {
  33. pii u = q.front();
  34. q.pop();
  35. for(int k=0; k<4; k++)
  36. {
  37. int tx=u.first+fx[k];
  38. int ty=u.second+fy[k];
  39. if(vis[tx][ty]==0 && isvalid(tx,ty))
  40. {
  41. vis[tx][ty]=1;
  42. d[tx][ty]=d[u.first][u.second]+1;
  43. q.push(make_pair(tx,ty));
  44. }
  45. }
  46. }
  47. }
  48.  
  49. int main()
  50. {
  51. //freopen("out.txt","w",stdout);
  52.  
  53. int bomb,temp,j_loop,j,enx,eny;
  54. while(scanf("%d%d",&r,&c)==2)
  55. {
  56. if(r==0&&c==0) break;
  57. CLR(gr);
  58. scanf("%d",&bomb);
  59.  
  60. for(int x=0; x<bomb; x++)
  61. {
  62. scanf("%d%d",&temp,&j_loop);
  63. for(int xx=1; xx<=j_loop; xx++)
  64. {
  65. scanf("%d",&j);
  66. gr[temp][j]=INT_MAX;
  67. }
  68. }
  69. scanf("%d%d",&stx,&sty);
  70. scanf("%d%d",&enx,&eny);
  71. bfsIn2D(stx,sty);
  72. printf("%d\n",d[enx][eny]);
  73. }
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement