Maruf_Hasan

crystal maze

Feb 1st, 2019
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define M 1010
  4. vector<char>adj[M];
  5. bool visited[M][M];
  6. int cell[M][M];
  7. int fx[]={1,-1,0,0};
  8. int fy[]={0,0,1,-1};
  9. int m,n;
  10.  
  11. int bfs(int x,int y)
  12. {
  13. visited[x][y]=true;
  14. pair<int,int>p,p1;
  15. int count=0;
  16. queue<pair<int,int> >q;
  17. q.push(make_pair(x,y));
  18. count=0;
  19. //dis[x][y]=0;
  20. while(!q.empty())
  21. {
  22. p=q.front();
  23. q.pop();
  24. for(int i=0;i<4;i++)
  25. {
  26. int tx=p.first+fx[i];
  27. int ty=p.second+fy[i];
  28. if(tx>=0 && tx<m && ty>=0 && ty<n && visited[tx][ty]==false && cell[tx][ty]==1)
  29. {
  30. if(adj[tx][ty]=='C'){
  31. count++;
  32. //dis[tx][ty]=dis[p.first][p.second]+1;
  33. }
  34. visited[tx][ty]=true;
  35. q.push(make_pair(tx,ty));
  36. }
  37. }
  38. }
  39.  
  40. return count;
  41. }
  42.  
  43.  
  44. int main()
  45. {
  46. int t,kase=0;
  47. scanf("%d",&t);
  48. while(kase<t)
  49. {
  50. int q,i,j;
  51. //char c;
  52. scanf("%d %d %d",&m,&n,&q);
  53. for(i=0;i<m;i++)
  54. {
  55. getchar();
  56. for(j=0;j<n;j++)
  57. {
  58. char c;
  59. scanf(" %c",&c);
  60. //getchar();
  61. if(c=='#'){
  62. visited[i][j]=true;
  63. cell[i][j]=-1;
  64. }
  65. else
  66. {
  67. cell[i][j]=1;
  68. visited[i][j]=false;
  69. }
  70. adj[i].push_back(c);
  71.  
  72. }
  73. }
  74. //getchar();
  75. //for(i=0;i<m;i++)
  76. //{
  77. // for(j=0;j<n;j++)
  78. // {
  79. // cout<<adj[i][j]<<" ";
  80. // }
  81. // cout<<endl;
  82. // }
  83.  
  84.  
  85. printf("Case %d:\n",kase+1);
  86. while(q--)
  87. {
  88. int x,y;
  89. scanf("%d %d",&x,&y);
  90. int ans=bfs(x-1,y-1);
  91. for(i=0;i<m;i++)
  92. {
  93. for(j=0;j<n;j++)
  94. {
  95. if(cell[i][j]==-1)
  96. visited[i][j]=true;
  97. else
  98. visited[i][j]=false;
  99. }
  100. }
  101. printf("%d\n",ans);
  102. }
  103.  
  104. for(i=0;i<m;i++)
  105. {
  106. adj[i].clear();
  107. }
  108. //memset(visited,false,sizeof visited);
  109. //memset(cell,0,sizeof cell);
  110.  
  111. kase++;
  112. }
  113.  
  114. return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment