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.

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXN = ;

 int dir[][] = {{-, }, {, }, {, -}, {, },};

 char g[MAXN][MAXN];

 int depth[MAXN][MAXN];

 bool vis[MAXN][MAXN];

 int n, m;

 char bg;

 bool circle;

 void init()

 {

     memset(g, '\0', sizeof(g));

     memset(depth, , sizeof(depth));

     memset(vis, false, sizeof(vis));

     circle = false;

 }

 bool check(int r, int c)

 {

     if (r <  || r >= n) {

         return false;

     }

     if (c <  || c >= m) {

         return false;

     }

     return true;

 }

 void dfs(int r, int c, int d)

 {

     if (circle) {

         return;

     }

     int i;

     int r2, c2;

     for (i = ; i < ; ++i) {

         r2 = r + dir[i][];

         c2 = c + dir[i][];

         if (!check(r2, c2)) {//越界

             continue;

         }

         if (g[r][c] != bg) {//不同

             continue;

         }

         if (!vis[r2][c2]) {//没访问过

             vis[r2][c2] = true;

             depth[r2][c2] = d + ;

             dfs(r2, c2, d + );

             depth[r2][c2] = ;

             vis[r2][c2] = false;

         } else if (d - depth[r2][c2] +  >= ) {//找到环

             circle = true;

             return;

         }

     }

 }

 int main()

 {

     int i, j;

     while (~scanf("%d%d", &n, &m)) {

         //init();

         for (i = ; i < n; ++i) {

             scanf("%s", g[i]);

         }

         circle = false;

         for (i = ; i < n; ++i) {

             for (j = ; j < m; ++j) {

                 bg = g[i][j];

                 vis[i][j] = true;

                 depth[i][j] = ;

                 dfs(i, j, );

                 depth[i][j] = ;

                 vis[i][j] = false;

                 if (circle) {

                     break;

                 }

             }

             if (circle) {

                 break;

             }

         }

         if (circle) {

             printf("Yes\n");

         } else {

             printf("No\n");

         }

     }

     return ;

 }