Fox And Two Dots

Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of size n × m cells, like this:

Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.

The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots d1, d2, ..., dk a cycle if and only if it meets the following condition:

1. These k dots are different: if i ≠ j then di is different from dj.

2. k is at least 4.

3. All dots belong to the same color.

4. For all 1 ≤ i ≤ k - 1: di and di + 1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge.

Determine if there exists a cycle on the field.Input

The first line contains two integers n and m (2 ≤ n, m ≤ 50): the number of rows and columns of the board.

Then n lines follow, each line contains a string consisting of m characters, expressing colors of dots in each line. Each character is an uppercase Latin letter.Output

Output "Yes" if there exists a cycle, and "No" otherwise.ExamplesinputCopy

3 4
AAAA
ABCA
AAAA

outputCopy

Yes

inputCopy

3 4
AAAA
ABCA
AADA

outputCopy

No

inputCopy

4 4
YYYR
BYBY
BBBY
BBBY

outputCopy

Yes

inputCopy

7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB

outputCopy

Yes

inputCopy

2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ

outputCopy

No

Note

In first sample test all 'A' form a cycle.

In second sample there is no such cycle.

The third sample is displayed on the picture above ('Y' = Yellow, 'B' = Blue, 'R' = Red).

public class solution {
    int[] dx = { 1, -1, 0, 0 };
    int[] dy = { 0, 0, 1, -1 };
    int[][] visited;
    int findCycle = 0;

    void dfs(String[] board, int x, int y, int fromX, int fromY, char needColor, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x].charAt(y) != needColor)
            return;
        if (visited[x][y] == 1) {
            findCycle = 1;
            return;
        }
        visited[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX == fromX && nextY == fromY)
                continue;
            dfs(board, nextX, nextY, x, y, needColor, n, m);
        }
    }

    int solve(String[] board, int n, int m) {
        visited = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (visited[i][j] == 0)
                    dfs(board, i, j, -1, -1, board[i].charAt(j), n, m);
        return findCycle;
    }
}