题解：P9243 [蓝桥杯 2023 省 B] 岛屿个数

Qianmo_su · 2025-04-11 00:43:07 · 题解

本题要求求一个地图中的岛屿数量，但是不包括子岛屿（在其它岛屿围成的环之间）。

对于求岛屿，可以使用搜索中的 Flood Fill 算法来实现，对每个为 1 的陆地进行 BFS，标记与它相邻的所有陆地。为了实现环内部的岛屿不被统计，我们可以先 BFS 海域，在 BFS 海域的过程中如果遍历到为 1 的陆地，就来一遍 Flood Fill 将其相邻的陆地全部打上标记，如果遍历到为 0 的海水就不入队（只有 0 会入队）。

需要注意的是，遍历海域是八个方向拓展的，而遍历陆地是四个方向扩展的。同时我们能保证海水拓展八个方向得到的岛屿都不在环内，这是因为陆地不入队，岛屿在环内的话是进不去的。可以借助下面样例来理解：

我们不可能遍历到 (3,2) 位置的 0 的，因为 0 不入队，遍历海域是进不到环内的，自然就遍历不到环内的 1 了。所以我们对于每次 Flood Fill，直接将答案加 1 就可以了。

还有一些需要注意的点：

我们需要确定遍历海水的起点。起点肯定要在最外面，所以我们默认图的下标从 1 开始，将 g_{0,i}、g_{i,0}、g_{n+1,i} 和 g_{i,m+1} 均设为 0，我们只需要从 (0,0) 位置开始遍历就可以了。
本题为多测，需要在每个测试数据都初始化一遍 vis 数组和存图的 g 数组（否则无法保证每次 g_{0,i}、g_{i,0}、g_{n+1,i} 和 g_{i,m+1} 均为 0）。

AC Code


#include <bits/stdc++.h>
using namespace std;

const int N = 55;
typedef pair<int,int> PII;

int n,m,ans;
char g[N][N];
bool vis[N][N];

int dx1[] = {1,0,-1,0},dy1[] = {0,1,0,-1};
int dx2[] = {-1,-1,0,1,1,1,0,-1},dy2[] = {0,1,1,1,0,-1,-1,-1};

void bfs1(int x,int y)
{
    ans++;
    queue<PII> q;
    q.push({x,y});
    vis[x][y] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i=0;i<4;i++)
        {
            int rx = x+dx1[i],ry = y+dy1[i];
            if(rx>=1 && rx<=n && ry>=1 && ry<=m && !vis[rx][ry] && g[rx][ry] == '1')
            {
                vis[rx][ry] = true;
                q.push({rx,ry});
            }
        }
    }
}

void bfs2()
{
    queue<PII> q;
    q.push({0,0});
    vis[0][0] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i=0;i<8;i++)
        {
            int rx = x+dx2[i],ry = y+dy2[i];
            if(rx>=0 && rx<=n+1 && ry>=0 && ry<=m+1 && !vis[rx][ry])
            {
                if(g[rx][ry] == '1') bfs1(rx,ry);
                else
                {
                    vis[rx][ry] = true;
                    q.push({rx,ry});
                }
            }
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        ans = 0;
        memset(vis,false,sizeof(vis));
        cin >> n >> m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> g[i][j];
        bfs2();
        cout << ans << endl;
    }
    return 0;
}