DFS【求连通块的数目】

整数m,n(m行，n列)矩阵。

细胞的个数。

分析：对图中的每个细胞都遍历一遍，走过的标记为1。遇到未被标记的细胞则从这个细胞开始搜索，细胞数目增1。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int maxn=505;
int m,n;
int vis[maxn][maxn];
char a[maxn][maxn];
int cnt=0;
int dir[4][2]={0,1,-1,0,0,-1,1,0};//四个方向
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(tx<0||tx>=m||ty<0||ty>=n)//边界判断
            continue;
        if(!vis[tx][ty]&&a[tx][ty]!='0'){//遇见未遍历过的细胞，继续搜索。
            vis[tx][ty]=1;//走过的地方标记为1
            dfs(tx,ty);
        }
    }
    return ;
}
int main()
{
    scanf("%d %d",&m,&n);
    for(int i=0;i<m;i++){
        scanf("%s",a[i]);
    }
    memset(vis,0,sizeof vis);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]!='0'&&!vis[i][j]){//遇到未遍历过的点，则从这个点开始遍历。
                vis[i][j]=1;//遍历过的细胞标记为1
                cnt++;//细胞数目增1
                dfs(i,j);
            }
        }
    }
    printf("%d
",cnt);
    return 0;
}