Advertisement
istinishat

DFS in Array

Aug 31st, 2016
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. #define si(a) scanf("%d",&a)
  8. #define MAX 1005
  9.  
  10. int X[]= {1,-1,0,0};
  11. int Y[]= {0,0,1,-1};
  12.  
  13. int vis[MAX][MAX];
  14. char str[MAX][MAX];
  15. bool is_circle;
  16.  
  17. void go(int nowx,int nowy,int fromx,int fromy)
  18. {
  19.     if(vis[nowx][nowy])
  20.     {
  21.         is_circle=true;
  22.         return ;
  23.     }
  24.     vis[nowx][nowy]=1;
  25.     int i;
  26.     for(i=0; i<4; i++)
  27.     {
  28.         int tox=nowx+X[i],toy=nowy+Y[i];
  29.         if((tox==fromx && toy==fromy) || str[nowx][nowy]!=str[tox][toy])
  30.             continue;
  31.         go(tox,toy,nowx,nowy);
  32.     }
  33.     return ;
  34. }
  35.  
  36. int main()
  37. {
  38.     int n,m,i,j;
  39.     si(n);
  40.     si(m);
  41.     for(i=0; i<n; i++)
  42.         scanf("%s",str[i]);
  43.     for(i=0; i<n; i++)
  44.     {
  45.         for(j=0; j<m; j++)
  46.         {
  47.             if(vis[i][j])
  48.                 continue;
  49.             go(i,j,-1,-1);
  50.         }
  51.     }
  52.     if(is_circle)
  53.         printf("Yes\n");
  54.     else
  55.         printf("No\n");
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement