连通块模板题

题目描述

一个 n×m
的方格图，一些格子被涂成了黑色，在方格图中被标为 1
，白色格子标为 0。
问有多少个四连通的黑色格子连通块。
四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。

输入

3 3(n×m)
1 1 1
0 1 0
1 0 1

输出

3

方法一(bfs)

//bfs
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int a[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool vis[N][N];
int n,m;
int ans;
queue<PII> q;
void bfs(int x,int y){
    q.push({x,y});
    a[x][y]=0;
    while(!q.empty()){
        PII t=q.front();
        int xx=t.first,yy=t.second;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=xx+dx[i];
            int ny=yy+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]==1){
                a[nx][ny]=0;
                q.push({nx,ny});
            }
        }
    }

}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)cin>>a[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(a[i][j]==1){
                bfs(i,j);
                ans++;
            }
        }
    cout<<ans;

    return 0;
}

方法二(dfs)

//bfs
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int a[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool vis[N][N];
int n,m;
int ans;
void dfs(int x,int y){
    a[x][y]=0;
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]==1){
            a[xx][yy]=0;
            dfs(xx,yy);
        }
    }

}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)cin>>a[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(a[i][j]==1){
                dfs(i,j);
                ans++;
            }
        }
    cout<<ans;

    return 0;
}