Tarango

Problem H

Jul 22nd, 2015
391
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 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 Max 9999999
  11.  
  12. struct pos{
  13.     int r;
  14.     int c;
  15.     pos(int a,int b){
  16.         r = a;
  17.         c = b;
  18.     }
  19. };
  20.  
  21. int row, col;
  22. char G[505][505];
  23. int taken[505][505];
  24. bool visited[505][505];
  25. int dx[] = {1,-1,0,0};
  26. int dy[] = {0,0,1,-1};
  27. int sr, sc, tr, tc;
  28.  
  29. int isValid(int r, int c) {
  30.     if (r <= 0 || c <= 0 || r > row || c > col)
  31.         return false;
  32.     return true;
  33. }
  34.  
  35. bool call() {
  36.     pos p(sr, sc);
  37.     visited[sr][sc] = true;
  38.     queue<pos> Q;
  39.     Q.push(p);
  40.     int rr, cc;
  41.     while (Q.empty() == false) {
  42.         pos cur = Q.front();
  43.         Q.pop();
  44.         //printf("Cur r: %d , c: %d\n",cur.r,cur.c);
  45.         if (cur.r == tr && cur.c == tc) {
  46.             return true;
  47.         }
  48.         for(int i = 0;i<4;i++){
  49.             rr = cur.r + dx[i];
  50.             cc = cur.c + dy[i];
  51.             if (isValid(rr, cc) == true && visited[rr][cc] == false) {
  52.                 if(G[rr][cc] == '.' || taken[rr][cc] >= 1){
  53.                     G[rr][cc] = '.';
  54.                     visited[rr][cc] = true;
  55.                     pos p(rr,cc);
  56.                     Q.push(p);
  57.                 }
  58.                 if(G[rr][cc] == '*'){
  59.                     taken[rr][cc]++;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     return false;
  65. }
  66.  
  67.  
  68. int main() {
  69.     string s;
  70.     int nCase;
  71.     //scanf("%d", &nCase);
  72.     cin >> nCase;
  73.     for (int cs = 1; cs <= nCase; cs++) {
  74.         //scanf("%d %d", &row, &col);
  75.         cin >> row >> col;
  76.         for (int i = 0; i < row; i++) {
  77.             cin >> s;
  78.             for (int j = 0; j < col; j++) {
  79.                 G[i+1][j+1] = s[j];
  80.             }
  81.         }
  82.         //scanf("%d %d %d %d", &sr, &sc, &tr, &tc);
  83.         cin >> sr >> sc >> tr >> tc;
  84.         //printf("sr: %d , sc: %d\n",sr,sc);
  85.         memset(taken,0,sizeof(taken));
  86.         memset(visited,false,sizeof(visited));
  87.         //printf("Taken Input\n");
  88.         bool res = call();
  89.         if(res == true) printf("YES\n");
  90.         else printf("NO\n");
  91.     }
  92. }
Advertisement
Add Comment
Please, Sign In to add comment