P8662 [蓝桥杯 2018 省 AB] 全球变暖--2024蓝桥杯冲刺省一

点击跳转例题

思路：
经典的连通块问题，记录连通块的时候，只要判断哪个连通块不会被淹没即可。
判断有没有淹没：只需要判断一个#周围有没有4个#即可，边界也算一个#。

代码：
 

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'
#define LL __int128

using namespace std;

const int N=2e5+10,M=1e3+10,mod=998244353,INF=0x3f3f3f3f;

char g[M][M];
bool st[M][M];

bool bfs(int x,int y,int n)
{
    queue<PII>q;q.push({x,y});
    st[x][y]=true;

    int dx[]={0,-1,0,1};
    int dy[]={-1,0,1,0};

    int flag=0;
    while (q.size())
    {
        PII t=q.front();q.pop();
        if(!flag)
        {
            int tmp=0;
            for(int i=0;i<4;i++)
            {
                int a=dx[i]+t.first;int b=dy[i]+t.second;
                if(a<1||a>n||b<1||b>n)
                {
                    tmp++;
                    continue;
                }
                if(g[a][b]=='#')
                {
                    tmp++;
                    continue;
                }
            }
            if(tmp==4)
                flag=1;
        }

        for(int i=0;i<4;i++)
        {
            int a=dx[i]+t.first;int b=dy[i]+t.second;
            if(a<1||a>n||b<1||b>n)continue;
            if(st[a][b])continue;
            if(g[a][b]=='.')continue;
            if(g[a][b]=='#')
            {
                q.push({a,b});
                st[a][b]=true;
            }
        }
    }
    return flag==1;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    //sum为总共的连通块个数，cnt为不会沉没的连通块。
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(!st[i][j]&&g[i][j]=='#')
            {
                if(bfs(i,j,n))
                    cnt++;
                sum++;
            }
        }
    cout<<sum-cnt<<endl;
    return 0;
}