这道题是我在看DFS的时候偶然发现有个大佬（https://blog.csdn.net/qq_41003528/article/details/81428672）的博客收录了有这么道题，既然这样就看一看吧
指路：http://codeforces.com/problemset/problem/510/B
思路：只要step>3并且沿着相同的字母一直走发现有已经标记的部分，则可以判断已经形成环
其中的坑：搜索到最后一个 A 时， 它会判断它前面的一个 A 是被搜过的，并且 满足 step ，会输出 yes
所以，综上，如果遇到被搜索过的相同字母并且不是上一步的位置并且满足step，那么就一定有环。
//https://blog.csdn.net/qq_41003528/article/details/81428672
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
using namespace std;
const int maxn=55;
char color;
char G[maxn][maxn];
int book[maxn][maxn];
int dir[4][2]={-1,0,0,1,
1,0,0,-1};
int m,n,flag;
bool judge(int x,int y,int nx,int ny){
if(nx>=0&&nx<m&&nx>=0&&ny<n&&!book[nx][ny]&&G[nx][ny]==G[x][y])
return true;
return false;
}
void dfs(int x,int y,int lx,int ly,int step)
{
if(flag)return ;
flag=0;
book[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(book[nx][ny]&&(lx!=nx||ly!=ny)&&step>=3&&color==G[nx][ny])
{
flag=1;
return ;
}
if(judge(x,y,nx,ny)){
dfs(nx,ny,x,y,step+1);
}
}
return ;
}
int main(){
cin>>m>>n;
for(int i=0;i<m;i++)
cin>>G[i];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(!book[i][j])
{
color=G[i][j];
dfs(i,j,0,0,0);
}
if(flag)break;
}
if(flag)break;
}
if(flag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
预期输出：
图片.png
真实输出：
图片.png
图片.png
最后文末：感谢大大https://blog.csdn.net/qq_41003528/article/details/81428672
