There are colorful flowers in the parterre in front of the door of college and form many beautiful patterns. Now, you want to find a circle consist of flowers with same color. What should be done ?

     Assuming the flowers arranged as matrix in parterre, indicated by a N*M matrix. Every point in the matrix indicates the color of a flower. We use the same uppercase letter to represent the same kind of color. We think a sequence of points d1, d2, … dk makes up a circle while:

    1. Every point is different.

    2. k >= 4

    3. All points belong to the same color.

    4. For 1 <= i <= k-1, di is adjacent to di+1 and dk is adjacent to d1. ( Point x is adjacent to Point y while they have the common edge).

    N, M <= 50. Judge if there is a circle in the given matrix. 

     There are multiply test cases.

     In each case, the first line are two integers n and m, the 2nd ~ n+1th lines is the given n*m matrix. Input m characters in per line. 

      Output your answer as “Yes” or ”No” in one line for each case. 

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 const int MAXN = 55; 5  6 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1},}; 7 char g[MAXN][MAXN]; 8 int depth[MAXN][MAXN]; 9 bool vis[MAXN][MAXN];10 int n, m;11 char bg;12 bool circle;13 14 void init()15 {16     memset(g, ‘\0‘, sizeof(g));17     memset(depth, 0, sizeof(depth));18     memset(vis, false, sizeof(vis));19     circle = false;20 }21 22 bool check(int r, int c)23 {24     if (r < 0 || r >= n) {25         return false;26     }27     if (c < 0 || c >= m) {28         return false;29     }30     return true;31 }32 33 void dfs(int r, int c, int d)34 {35     if (circle) {36         return;37     }38     int i;39     int r2, c2;40     for (i = 0; i < 4; ++i) {41         r2 = r + dir[i][0];42         c2 = c + dir[i][1];43         if (!check(r2, c2)) {//越界44             continue;45         }46         if (g[r][c] != bg) {//不同47             continue;48         }49         if (!vis[r2][c2]) {//没访问过50             vis[r2][c2] = true;51             depth[r2][c2] = d + 1;52             dfs(r2, c2, d + 1);53             depth[r2][c2] = 0;54             vis[r2][c2] = false;55         } else if (d - depth[r2][c2] + 1 >= 4) {//找到环56             circle = true;57             return;58         }59     }60 }61 62 int main()63 {64     int i, j;65 66     while (~scanf("%d%d", &n, &m)) {67         //init();68         for (i = 0; i < n; ++i) {69             scanf("%s", g[i]);70         }71         circle = false;72         for (i = 0; i < n; ++i) {73             for (j = 0; j < m; ++j) {74                 bg = g[i][j];75                 vis[i][j] = true;76                 depth[i][j] = 1;77                 dfs(i, j, 1);78                 depth[i][j] = 0;79                 vis[i][j] = false;80                 if (circle) {81                     break;82                 }83             }84             if (circle) {85                 break;86             }87         }88         if (circle) {89             printf("Yes\n");90         } else {91             printf("No\n");92         }93     }94 95     return 0;96 }