蓝桥杯2023岛屿个数

题目描述

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

在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),...,(xk−1,yk−1)(x_0,y_0),(x_1,y_1),...,(x_{k-1},y_{k-1})，其中 (x(i+1)%k,y(i+1)%k)(x_{(i+1)\%k},y_{(i+1)\%k}) 是由 (xi,yi)(x_i,y_i) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)(0≤i≤k-1)，此时这 k 个格子就构成了一个"环"。

如果另一个岛屿 B 所占据的格子全部位于这个"环"内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。

若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。

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

输入格式

第一行一个整数 TT，表示有 TT 组测试数据。

接下来输入 TT 组数据。

对于每组数据，第一行包含两个用空格分隔的整数 MM、NN 表示地图大小；接下来输入 MM 行，每行包含 NN 个字符，字符只可能是 0 或 1。

输出格式

对于每组数据，输出一行，包含一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

样例输出 #1

1
2
1
3

样例解释 #1

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：

1
2
3
4
5
01111
11001
10201
10001
11111

岛屿 2 在岛屿 1 的"环"内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。

对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

1
2
3
4
5
111111
100001
020301
100001
111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有"环"。

提示

对于 30% 的评测用例，1≤M,N≤101≤M,N≤10。

对于 100% 的评测用例，1≤T≤101≤T≤10，1≤M,N≤501≤M,N≤50。

code

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,ans;
const int N=55;
int a[N][N];
bool sea[N][N],load[N][N];// sea 标记海洋是否访问过，load 标记陆地是否访问过
int dx[8]={-1,0,1,0,-1,-1,1,1};// 8个方向
         //上，左，下，右，左上，右上，右下，左下
int dy[8]={0,-1,0,1,-1,1,1,-1};
int ddx[4]={-1,0,1,0};// 4个方向
        //上，左，下，右
int ddy[4]={0,-1,0,1};

bool check(int x,int y){//判断是否越界
    return (x>=0&&x<n&&y>=0&&y<m);
}
//找到了x,y所在的岛屿，并且把该岛屿中的其他的1都标记成了true。
void bfs_load(int x,int y){
    queue<pii>q;
    load[x][y]=true;//标记一下走过了
    q.push({x,y});
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){//遍历四个方向
            int lx=t.first+ddx[i];
            int ly=t.second+ddy[i];
            if(check(lx,ly)&&a[lx][ly]&&!load[lx][ly]){// 如果相邻点是陆地且未访问过，则加入队列
                load[lx][ly]=true;
                q.push({lx,ly});
            }
        }
    }
}



void bfs_sea(int x,int y){
    queue<pii>q;
    sea[x][y]=true;//标记一下走过了
    q.push({x,y});
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<8;i++){//遍历八个方向
            int sx=t.first+dx[i];
            int sy=t.second+dy[i];
            if(check(sx,sy)&&!sea[sx][sy]&&!a[sx][sy]){// 如果相邻点是海洋且未访问过，则加入队列
                sea[sx][sy]=true;
                q.push({sx,sy});
            }
            if(check(sx,sy)&&!load[sx][sy]&&a[sx][sy]){// 如果相邻点是陆地且未访问过，则增加答案并遍历该陆地
                ans++;
                bfs_load(sx,sy);
            }
        }
    }
}

void solve(){
    ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            a[i][j]=s[j]-'0';
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            sea[i][j]=load[i][j]=false;//多组数据 每次都初始化一下
        }
    }
    bool flag=false;
    for(int i=0;i<n;i++){//遍历四条边 也可以用下面注释的方法遍历
        for(int j=0;j<m;j++){
            if(i==0||i==n-1||j==0||j==m-1){
                if(!a[i][j]&&!sea[i][j]){
                    flag=true;
                    bfs_sea(i,j);
                }
            }
        }
    }
    // for(int i=0;i<m;i++){//第一行
    //     if(!a[0][i]&&!sea[0][i]){
    //         flag=true;
    //         bfs_sea(0,i);
    //     }
    // }
    // for(int i=1;i<n;i++){//第一列
    //     if(!a[i][0]&&!sea[i][0]){
    //         flag=true;
    //         bfs_sea(i,0);
    //     }
    // }
    // for(int i=1;i<m;i++){//最后一行
    //     if(!a[n-1][i]&&!sea[n-1][i]){
    //         flag=true;
    //         bfs_sea(n-1,i);
    //     }
    // }
    // for(int i=1;i<n-1;i++){//最后一列
    //     if(!a[i][m-1]&&!sea[i][m-1]){
    //         flag=true;
    //         bfs_sea(i,m-1);
    //     }
    // }
    if(!flag){//防止全是墙壁的情况 全是墙壁的情况也是一座岛
        ans=1;
    }
    cout<<ans<<endl;
}

int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    
    return 0;
}