Codeforces-----510B Fox And Two Dots 搜索

E - E Time Limit:2000MS    Memory Limit:262144KB    64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 510B

Description

Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of sizen × 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 dotsd₁, d₂, ..., d_k acycle if and only if it meets the following condition:

These k dots are different: if i ≠ j then d_i is different fromd_j.k is at least 4. All dots belong to the same color. For all 1 ≤ i ≤ k - 1: d_i and d_i + 1 are adjacent. Also,d_k andd₁ should also be adjacent. Cellsx 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 andm (2 ≤ n, m ≤ 50): the number of rows and columns of the board.

Then n lines follow, each line contains a string consisting ofm 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.

Sample Input

Input 3 4 AAAA ABCA AAAA Output Yes Input 3 4 AAAA ABCA AADA Output No Input 4 4 YYYR BYBY BBBY BBBY Output Yes Input 7 6 AAAAAB ABBBAB ABAAAB ABABBB ABAAAB ABBBAB AAAAAB Output Yes Input 2 13 ABCDEFGHIJKLM NOPQRSTUVWXYZ

Output No

给一幅图，问是否能构成环，没想到什么好的方法，暴力过，每个点都搜索一遍看能不能从这点出发再回到这个点路程不小于4

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 100010 #define inf 0x3f3f3f3f #define ll long long using namespace std; int map[55][55]; bool vis[55][55]; int mov[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; int ans, ok, n, m, s, e; void dfs(int x, int y){ if(ok){ return ; } if(vis[x][y]){ if(ans >= 4 && x == s && y == e){//只需检查是否从一个点出发再次回到这个点并且路程不小于4 ok++; } return ; } vis[x][y] = true; for(int i = 0; i < 4; i++){ if(map[x+mov[i][0]][y+mov[i][1]] != map[x][y]){ continue; } ans++; dfs(x+mov[i][0], y+mov[i][1]); ans--; } return ; } int main(){ int t, kcase = 1; char ch; while(~scanf("%d%d", &n, &m)){ memset(map, -1, sizeof(map)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf(" %c", &ch); map[i][j] = ch-64;//便于判断边界，直接memset初始化-1 } } ok = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ memset(vis, false, sizeof(vis)); ans = 1; s = i; e = j; dfs(i, j); if(ok){ break; } } if(ok){ break; } } printf(ok ? "Yes\n" : "No\n"); } return 0; }