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

· · 题解

题目要求求主岛屿个数，即求接触到最外层流入的海水的岛屿个数。直接判断一个岛屿是否是另一个岛屿的子岛屿不好判断，所以不如放弃掉子岛屿，而只关注主岛屿的个数，换句话说，只要接触到从最外层流入的海水的岛屿都一定是主岛屿。

不过，一个主岛屿如果不是通过严格的上下左右操作形成一个环，而是存在类似样例二的斜跨格子的情况，那么该主岛屿并不形成环，换句话说就是海水可以通过斜跨格子的方式流入。

将上述思路运用在代码中就会有以下要点：

  1. 海水流入的方向应当有上、下、左、右、左上、右上、左下、右下，八种方向进行操作。
  2. 判断岛屿是否是联通，必须严格按照上、下、左、右，四个方向进行连接。
  3. 与海水直接接触的岛屿必然是主岛屿。

理解以上要点后，思路就出来了。首先，在地图的最外圈遍历，如果遇到海水 0，即需要做八个方向的 bfs 操作。在海水的 bfs 操作中，如果遇到了主岛屿 1，则直接对该点进行四个方向的 bfs 操作，并记录答案。

需要注意的是，如果是从所给地图的最外圈进行遍历判断，则需要注意最外圈全部被主岛屿 1 占满的情况，此时答案应特判为 1。若是从地图最外圈的更外一圈，也就是虚构的海水进行 bfs 操作，则无需担心该特判问题。（本题解代码用的是前者方式）

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
int t,n,m,res;
bool vis[N][N];
char mp[N][N];
int nextStep[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
struct inner{
    int x,y;
};

void bfs1(int x,int y){
    queue<inner> que;
    que.push({x,y});
    res++;

    while(!que.empty()){
        auto tt = que.front();
        que.pop();

        for(int i=0;i<4;i++){
            int tx = tt.x + nextStep[i][0];
            int ty = tt.y + nextStep[i][1];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[tx][ty]=='1'&&!vis[tx][ty]){
                que.push({tx,ty});
                vis[tx][ty] = true;
            }
        }
    }
}

void bfs0(int x,int y){
    queue<inner> que;
    que.push({x,y});
    vis[x][y] = true;

    while(!que.empty()){
        auto tt = que.front();
        que.pop();

        for(int i=0;i<8;i++){
            int tx = tt.x + nextStep[i][0];
            int ty = tt.y + nextStep[i][1];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!vis[tx][ty]){
                vis[tx][ty] = true;
                if(mp[tx][ty]=='1') bfs1(tx,ty);
                else que.push({tx,ty});
            }
        }
    }
}

void solve(){
    bool flag = false;
    res = 0;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin >> mp[i][j];
            vis[i][j] = false;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(i==1 || i==n || j==1 || j==m)//对边缘的海水进行 bfs0
                if(!vis[i][j] && mp[i][j] == '0'){
                    bfs0(i,j);
                    flag = true;
                }
    if(!flag) res = 1;//以防一个岛屿占满了外边界的情况
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}