蓝桥杯2023年第十四届省赛真题-岛屿个数 | vegeone

vegeone
0%

蓝桥杯2023年第十四届省赛真题-岛屿个数

发表于 更新于 分类于 Valine：

题意

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。

在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：，其中是由 通过上/下/左/右移动一次得来的 ，此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

思路

题目简而言之，就是有很多岛屿，会出现大岛屿包着小岛屿的情况（这种情况只算一个岛屿），求岛屿数量

主体思路就是先把整张图划分为河流与大岛屿，各个大岛屿之间通过河流分割，大岛屿内部的河流直接用1填补，这样就避免了小岛屿、大岛屿之间的影响。然后剩下来没发现一个大岛屿，进行记数并将整个岛屿覆盖为河流。

代码

  1. 将地图划分为河流与大岛屿时，为了区分是岛屿内的河流还是岛与岛之间的河流，分别用0和2表示，由于不好确定岛与岛之间的河流的起点，所以之间在整个地图外边围了一圈设为河流（这些格子是保证赋值为2的）。

  2. 根据题目中环的定义来看，两个岛只有在四联通的其中一种时才算相连，因此在dfs河流的时候还需要遍历斜对角的格子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=55;
typedef pair<int,int>pp;
int num[N][N];
int m,n;
int d[8][2]={{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
bool check(int x,int y){
    return x>=0&&x<=m+1&&y>=0&&y<=n+1;
}
void dfs1(int x,int y){
    num[x][y]=2;
    for(int i=0;i<8;++i){
        int tx=x+d[i][0],ty=y+d[i][1];
        if(num[tx][ty]==0&&check(tx,ty)){
            dfs1(tx,ty);
        }
    }
}
void dfs2(int x,int y){
    num[x][y]=2;
    for(int i=0;i<4;++i){
        int tx=x+d[i][0],ty=y+d[i][1];
        if(num[tx][ty]==1&&check(tx,ty)){
            dfs2(tx,ty);
        }
    }
}
void solve()
{
    
    cin>>m>>n;
    for(int i=0;i<=m+1;++i){
        for(int j=0;j<=n+1;++j){
            num[i][j]=0;
        }
    }
    for(int i=1;i<=m;++i){
        string str;
        cin>>str;
        for(int j=1;j<=n;++j){
            num[i][j]=str[j-1]-'0';
        }
    }
    dfs1(0,0);
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(!num[i][j])num[i][j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(num[i][j]==1){
                ++ans;
                // cerr<<i<<" "<<j<<endl;
                dfs2(i,j);
            }
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)	solve();
    return 0;
}