CodeForces 510BFox And Two Dots（dfs）

Description 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. 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 Hint 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).

题意：一个小游戏，给你一个矩阵，其中相同字母可以相连，问你图中是否有相同字母围成的圈。

思路：这道题我用dfs写的。首先对于每次输入的字母保存其个数（因为至少有四个相同字母才能围成圈）。然后对于每个大于四的字母进行dfs。搜索的时候判断条件是

if(vis[x][y]||x<0||x>=n||y<0||y>=m||map[x][y]!=s) return;s代表这个字母，相同字母才继续搜索。

大概做法就是对于每次搜索的相同字母保存其父节点坐标。记录第一个搜索的坐标，下次访问这个坐标的时候判断访问这个坐标的点是不是他的父节点，不是的话就说明是通过另一个点访问到的，就围成了一个圈。这时有个bug就是dfs是四个方向，搜索第二个坐标时还会访问第一个坐标，所以要加一个判断

if(x==s1&&y==e1&&q!=-1&&w!=-1) { if(vv[q][w].x!=s1||vv[q][w].y!=e1) flag=true; }就是判断第一个坐标是不是这个坐标的父节点，是的话没有围成圈继续，不是的话围成圈flag=true。

代码：

#include<cstdio> #include<cstring> #include<math.h> using namespace std; int n,m; char map[60][60];//记录字母 int sh[500];//记录每个字母的个数 int vis[60][60];//是否访问过 char s;//保存搜索的字母 bool flag;//判断是否围成圈 int q,w;//保存这个点坐标 struct st{ int x; int y; }vv[60][60]; //保存父节点坐标 int s1,e1; void dfs(int x,int y) { if(x==s1&&y==e1&&q!=-1&&w!=-1)//判断是否围成圈，下次访问第一个点时是不是通过另一个点访问的 { if(vv[q][w].x!=s1||vv[q][w].y!=e1)//排除子节点重新访问该点 flag=true; } if(vis[x][y]||x<0||x>=n||y<0||y>=m||map[x][y]!=s)//搜索条件 return; vv[x][y].x=q,vv[x][y].y=w; vis[x][y]=1; if(!flag) // 因为没有将q,w直接输在dfs中，所以每次dfs前都要保存坐标防止dfs一个方向失败后qw变化 { q=x,w=y; dfs(x+1,y); q=x,w=y; dfs(x-1,y); q=x,w=y; dfs(x,y+1); q=x,w=y; dfs(x,y-1); } } int main() { while(~scanf("%d%d",&n,&m)) { flag=false; memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); memset(sh,0,sizeof(sh)); memset(vv,0,sizeof(vv)); int i=0,j=0; for(i=0;i<n;i++)// 输入并保存个数 { scanf("%s",map[i]); for(j=0;j<m;j++) sh[map[i][j]]++; } for(i=0;i<n;i++)//初始化每个点的父节点为自己 for(j=0;j<m;j++) vv[i][j].x=i,vv[i][j].y=j; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(sh[map[i][j]]>=4&&!vis[i][j])//个数超过四搜索 ,!vis[i][j]可以防止相同字母重复搜索 { memset(vis,0,sizeof(vis));//每次搜索 清空防止有两种字母都超过四个 s1=i,e1=j;//保存第一个搜索点坐标 flag=false; s=map[i][j];//保存初始点字母 q=-1,w=-1; dfs(i,j); } if(flag) break; } if(flag) break; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }