题目描述

连通块问题 bfs

算法1

(bfs) $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
typedef pair<int ,int> PII;
int n,m,cnt;
char g[N][N];
int st[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void bfs (int x,int y,int &sum,int &bound)//&  之后要使用到所以用引用
{
    queue<PII> q;
    q.push({x,y});//把找到的第一个#入队
    st[x][y]++;//标记
    while(q.size())
    {
        bool is=false;//标记是否是会被淹没的陆地
        auto t=q.front();
        q.pop();
        sum++;//一片岛屿的陆地总数
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<1||a>n||b<1||b>n) continue;
            else if(st[a][b]) continue;
            else if(g[a][b]=='.')
            {
                //此处搜到的不是# 不用标记
                is=true;//邻近的陆地要被淹没
                continue;
            }
            st[a][b]++;//标记下一块陆地
            q.push({a,b});//陆地入队
        }
        if(is) bound++;//要被淹没的陆地加一
    }
    return ;
}
int main()
{
    cin>>n;
    memset(g,'.',sizeof g);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>g[i][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        if(g[i][j]=='#'&&!st[i][j])
        {
            int sum=0;int bound=0;
            bfs(i,j,sum,bound);
            if(sum==bound)//当岛屿的所有陆地和被淹没的陆地相等时
                cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}