福克斯在玩一款手机解迷游戏，这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样：
每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。
这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点，形成了一个环。一般的，我们将一个序列 d1,d2,...,dk 看成一个环，当且仅当它符合下列条件时：
1. 这k个点不一样，即当 i≠j时， di 和 dj不同。
2. k至少是4。
3. 所有的点是同一种颜色。
4. 对于所有的 1≤i≤k-1: di 和 di+1 是相邻的。还有 dk 和 d1 也应该相邻。单元 x 和单元 y 是相邻的当且仅当他们有公共边。
当给出一幅格点时，请确定里面是否有环。
Input
单组测试数据。 第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。 接下来n行，每行包含一个有m个字母的串，表示当前行每一个点的颜色。每一个字母都是大写字母。
Output
如果有环输出Yes，否则输出No。
Input示例
3 4 AAAA ABCA AAAA 3 4 AAAA ABCA AADA
Output示例
Yes No
1，dfs的思路就是暴力搜索，不往回搜(这步很重要)，如果搜索的点标记过则有环，输出Yes，否则输出No
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; char s[55][55]; int visit[55][55]; int dir[4][2]={-1,0, 1,0, 0,-1, 0,1}; int n,m,flag; void dfs(int x,int y,int sum,char ch)//x,y为坐标，ch是要搜索的字符，sum是搜索方向，0是上，1是下，2是左，3是右 { if(x<0||x>n||y<0||y>m||ch!=s[x][y])//越界和不符合条件 return ; if(visit[x][y]==1)//搜索终点，找到之前搜索过的 { flag=1; return ; } if(flag) return; visit[x][y]=1; for(int i=0;i<4;i++) { if(sum==0&&i==1) continue;//如果是从向上搜索过来的，就不往下搜索 if(sum==1&&i==0) continue;//往下搜索过来的，不往上搜索 if(sum==2&&i==3) continue;//往左搜索过来的，不往右搜索 if(sum==3&&i==2) continue;//往右搜索过来的，不往左搜索 int dx=x+dir[i][0]; int dy=y+dir[i][1]; dfs(dx,dy,i,ch); } } int main() { while(cin>>n>>m) { flag=0; memset(visit,0,sizeof(visit)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>s[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!visit[i][j])//搜索每一个字母 dfs(i,j,-1,s[i][j]); } if(flag==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
2.并查集思路：往下，往右走，如果字母相同，则令成同一祖先。如果有环，就成了矩形，矩形是关于对角线对称的，往下的会使最后的顶点先变成祖先相等，之后往右则和最后顶点祖先相等，则标记，退出循环就好。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int fa[3000]; char s[60][60]; int find(int x)//查询祖先 { if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } bool unionn(int x,int y)//连通祖先 { x=find(x); y=find(y); if(x==y) return true;//祖先相等则返回正确 fa[x]=y; return false; } int main() { int n,m; while(cin>>n>>m) { bool flag=false; for(int i=0;i<=n*m;i++)//每个点按矩阵编号1到n*m fa[i]=i; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>s[i][j]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(i!=n-1&&s[i][j]==s[i+1][j]&&unionn(i*m+j,(i+1)*m+j))//往下走 flag=!flag; if(j!=m-1&&s[i][j]==s[i][j+1]&&unionn(i*m+j,i*m+j+1))//往右走，碰到祖先相等则有环 flag=!flag; if(flag) break; } if(flag) break; } if(flag) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }