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:
- These k dots are different: if i ≠ j then di is different from dj.
- k is at least 4.
- All dots belong to the same color.
- 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.
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 "Yes" if there exists a cycle, and "No" otherwise.
3 4
AAAA
ABCA
AAAA
Yes
3 4
AAAA
ABCA
AADA
No
4 4
YYYR
BYBY
BBBY
BBBY
Yes
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
Yes
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
No
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).
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <stack> 12 using namespace std; 13 const int INF = 0x7fffffff; 14 const double EXP = 1e-8; 15 const int MS = 55; 16 int n, m, cnt; 17 18 char cell[MS][MS]; 19 int vis[MS][MS]; 20 int dir[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 }; 21 22 bool dfs(char c, int sx, int sy, int x, int y) 23 { 24 if (sx == x&&sy == y&&vis[sx][sy]) 25 { 26 return cnt >= 4 ? true : false; 27 } 28 vis[x][y] = 1; 29 for (int i = 0; i < 4; i++) 30 { 31 int tx = x + dir[i][0]; 32 int ty = y + dir[i][1]; 33 if (tx >= 0 && tx < n&&ty >= 0 && ty < m&&cell[tx][ty] == c&&vis[tx][ty] == 0 || (tx == sx&&ty == sy)) 34 { 35 cnt++; 36 if (dfs(c, sx, sy, tx, ty)) 37 return true; 38 cnt--; 39 } 40 } 41 return false; 42 } 43 44 45 bool solve() 46 { 47 for (int i = 0; i < n; i++) 48 { 49 for (int j = 0; j < m; j++) 50 { 51 memset(vis, 0, sizeof(vis)); 52 cnt = 0; 53 if (dfs(cell[i][j], i, j, i, j)) 54 return true; 55 } 56 } 57 return false; 58 } 59 int main() 60 { 61 cin >> n >> m; 62 for (int i = 0; i < n; i++) 63 cin >> cell[i]; 64 if (solve()) 65 cout << "Yes" << endl; 66 else 67 cout << "No" << endl; 68 return 0; 69 }