求问大佬,用的dfs,为啥加了一行就AC了?自己都没想清楚
查看原帖
求问大佬,用的dfs,为啥加了一行就AC了?自己都没想清楚
239716
Haron楼主2022/5/16 19:48

以下是代码,加的就是dfs第一行的st[x][y]判断为1则返回。我这里st记录的就是类似于连通块了,但是我想的是不用这行代码直接判断f[x][y]=0(就是原矩阵判断到不是细胞的)就能结束了,但是这样搞程序就崩溃了??我的思路是一直不断搜索附近的矩阵直到遇到不是细胞数字的时候,为啥加了一个st[x][y]判断就ac了呀?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
int st[N][N];
int n,m,ans;
char a[N];
void dfs(int x,int y)
{
    if(st[x][y]) return;
    st[x][y]=1;
    //处理边界
    if(f[x][y]==0) return;
    //处理分支
    dfs(x+1,y);
    dfs(x,y+1);
    dfs(x-1,y);
    dfs(x,y-1);
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        for(int j=0;j<m;j++)
        {
            int x=a[j]-48;
            if(x>=1&&x<=9) f[i][j+1]=1;
        }
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         if(f[i][j]==1&&(!st[i][j])) 
         {
             dfs(i,j);
             ans++;
         }
     }
    cout<<ans<<endl;
    return 0;
}
2022/5/16 19:48
加载中...