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

yurril · 2025-04-09 19:48:13 · 题解

这一题是数岛屿数量的进阶题目，难点在于如何判断该岛屿是否为子岛屿。我们可以将海域分为内海和外海，内海即由岛屿形成的环形区域内的海域。判断一个岛屿是否为子岛屿的关键在于其是否能到达外海。注意，在 dfs 染色时，我们从上下左右方向进行遍历，而在判断能否到达外海时，则需要从四面八方进行遍历。

贴上 AC 代码，（代码有注释） qwq

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll=long long;
char mp[60][60];
int vis[60][60]; // 经典 dfs 标记
int sc; // 染色编号
int v[60][60]; // 在查找该岛屿能否走到外海的标记
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dx1[]={1,1,1,0,0,-1,-1,-1};
int dy1[]={0,1,-1,1,-1,0,1,-1};
int n,m,ans;
void dfs(int x,int y){
    vis[x][y]=sc;
    for(int i=0;i<4;i++){ // 从上下左右遍历，将岛屿染色
        int nx=dx[i]+x;
        int ny=dy[i]+y;
        if(vis[nx][ny]||nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='0')continue;
        dfs(nx,ny);
    }
} 
bool query(int x,int y){
    if(x>n||x<1||y>m||y<1)return 1;
    v[x][y]=1;
    for(int i=0;i<8;i++){ // 观察是否能走到外海要从四面八方遍历
        int nx=dx1[i]+x;
        int ny=dy1[i]+y;
        if((mp[nx][ny]=='1'&&vis[nx][ny]!=sc)||v[nx][ny])continue; // 要沿着海域走，不能走到其他岛屿上，但是可以在本岛领土走
        if(query(nx,ny))return 1;
    }
    return 0;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            vis[i][j]=0;
        }
    }
    ans=0; // 全局变量 ans 归零
    sc=0; // 编号归零
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j]||mp[i][j]=='0')continue;
            sc++;
            dfs(i,j);
            for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)v[i][j]=0; // 将v标记全部还原为 0
            if(query(i,j))ans++; // 如果能走到外海就说明不是子岛屿
        }
    }
    cout<<ans<<endl;
}
int main() {
    ios::sync_with_stdio(false);                                                                       
    cin.tie(nullptr);
    int t=1;cin>>t;
    while(t--)solve();

}