走环（入门dfs）

这道题是我在看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