【CodeForces】510B - Fox And Two Dots（bfs）

点击打开题目

B. Fox And Two Dots time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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.

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.

Examples 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 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).

从前到最后进行一次bfs，在每一个点向四周搜索（但是不能走回头路），每搜到一个点就用vis标记一下。

如果搜到了vis标记过的点，而且和这个点是同一种颜色，那么说明肯定打环了，说明就成立。

代码如下：

#include <stdio.h> #include <cstring> #include <algorithm> using namespace std; #define CLR(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define LL long long int h,w; char mapp[55][55]; bool vis[55][55]; int mx[4] = {0,0,1,-1}; int my[4] = {1,-1,0,0}; bool ans; void bfs(int x,int y,int fx,int fy) { if (vis[x][y]) { ans = true; return; } vis[x][y] = true; int nx,ny; for (int i = 0 ; i < 4 ; i++) { nx = x + mx[i]; ny = y + my[i]; if (nx == fx && ny == fy) continue; if (mapp[nx][ny] == mapp[x][y]) bfs(nx,ny,x,y); } } int main() { while (~scanf ("%d %d",&h,&w)) { ans = false; for (int i = 1 ; i <= h ; i++) scanf ("%s",mapp[i]+1); CLR(vis,false); for (int i = 1 ; i <= h ; i++) { for (int j = 1 ; j <= w ; j++) { if (!vis[i][j]) bfs(i,j,i,j); if (ans) break; } if (ans) break; } printf (ans ? "Yes\n" : "No\n"); } return 0; }