P1451 求细胞数量——题解

解题思路

扫描每个格子。遇到尚未访问的非零格子时，说明发现了一个新细胞，答案加一，并从该格开始 DFS，把上下左右连通的全部非零格标记为已访问。可以直接把访问过的格子改成字符 0。

正确性说明

一次 DFS 恰好访问从起点可通过四方向到达的全部非零格，因此恰好覆盖一个连通块。主循环只在未访问非零格上启动 DFS，所以每个细胞被统计一次且仅一次。

复杂度分析

时间复杂度 $O(nm)$，最坏递归空间 $O(nm)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,m; char g[105][105];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfs(int x,int y){
    g[x][y]='0';
    for(int k=0;k<4;k++){
        int nx=x+dx[k],ny=y+dy[k];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]!='0') dfs(nx,ny);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>(g[i]+1);
    int ans=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]!='0'){
        ans++; dfs(i,j);
    }
    cout<<ans<<'\n'; return 0;
}

#include <bits/stdc++.h> using namespace std; int n,m; char g[105][105]; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; void dfs(int x,int y){ g[x][y]='0'; for(int k=0;k<4;k++){ int nx=x+dx[k],ny=y+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]!='0') dfs(nx,ny); } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>(g[i]+1); int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]!='0'){ ans++; dfs(i,j); } cout<<ans<<'\n'; return 0; }