Maruf_Hasan

crystal mara dise

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