HZAU 1208 Color Circle （dfs）

Description

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:Every point is different.k >= 4All points belong to the same color.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.

Input

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

Output your answer as “Yes” or ”No” in one line for each case.

Sample Input

3 3AAAABAAAA

Sample Output

Yes

题意

对于一张地图，判断能否找到一条路线，长度大于4，相同字母，并且回到原点。

思路

找图中的一个环，可以从某个点进入开始 dfs ，标记已经访问过的点，如果遍历过程中遇到它们，则找到一个环，输出 ​​Yes​​​ ，否则输出 ​​No​​ 。

时间复杂度： O(n×m)

AC 代码

#include#include#include#includeusing namespace std;#define MAXX 110000int n,m;int mapp[55][55];bool vis[55][55];int mv[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};bool flag;void dfs(int x,int y,int xa,int ya) // (x,y) 为当前点坐标， (xa,ya) 为它从哪个点来{ for(int i=0; i<4; i++) // 四个方向 { int xi=x+mv[i][0]; int yi=y+mv[i][1]; if(xi<0||xi>=n||yi<0||yi>=m||mapp[xi][yi]!=mapp[x][y])continue; // 要求搜索的点相同 if(!vis[xi][yi]) { vis[xi][yi]=true; dfs(xi,yi,x,y); if(flag)return; } else { if(xi==xa&&yi==ya)continue; // 忽略来的那一点，如果还遇到一个已经访问的点，则是一个环 flag=true; return; } }}void solve(){ for(int i=0; i>n>>m) { string c; memset(vis,false,sizeof(vis)); flag=false; for(int i=0; i>c; for(int j=0; j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。