Tarango

Untitled

Nov 13th, 2015
239
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. //============================================================================
  2. // Name        : ACM
  3. // Author      : Tarango Khan
  4. // Team        : BRACU Byteheads
  5. //============================================================================
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #define Size 100005
  10. #define Mod 1000000007
  11. #define INF 999999999999999
  12.  
  13. char Mat[1001][1001];
  14. int R,C,K;
  15. int DP[1001][1001];
  16. bool visited[1001][1001];
  17.  
  18. int dx[] = {1,-1,0,0};
  19. int dy[] = {0,0,1,-1};
  20.  
  21. int cnt = 0;
  22. void DFS1(int r,int c){
  23.     visited[r][c] = true;
  24.     for(int i = 0;i<4;i++){
  25.         int rr = dx[i]+r;
  26.         int cc = dy[i]+c;
  27.         if(Mat[rr][cc] == '*'){
  28.             cnt++;
  29.             continue;
  30.         }
  31.         if(visited[rr][cc] == true) continue;
  32.         DFS1(rr,cc);
  33.     }
  34. }
  35.  
  36. void DFS2(int r,int c){
  37.     if(DP[r][c] != -1){
  38.         return;
  39.     }
  40.     DP[r][c] = cnt;
  41.     for(int i = 0;i<4;i++){
  42.         int rr = dx[i]+r;
  43.         int cc = dy[i]+c;
  44.         if(Mat[rr][cc] == '*'){
  45.             continue;
  46.         }
  47.         DFS2(rr,cc);
  48.     }
  49. }
  50.  
  51. int main() {
  52.     int x,y;
  53.     scanf("%d %d %d",&R,&C,&K);
  54.     for(int i = 0;i<R;i++){
  55.         scanf("%s",Mat[i]);
  56.     }
  57.     memset(DP,-1,sizeof(DP));
  58.     memset(visited,false,sizeof(visited));
  59.     for(int i = 0;i<K;i++){
  60.         scanf("%d %d",&x,&y);
  61.         x--;y--;
  62.         cnt = 0;
  63.         if(DP[x][y] != -1){
  64.             cnt = DP[x][y];
  65.         }else{
  66.             DFS1(x,y);
  67.             DFS2(x,y);
  68.         }
  69.         printf("%d\n",cnt);
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment