题目描述

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

在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0​,y0​),(x1​,y1​),…,(xk−1​,yk−1​)，其中 (x(i+1)modk​,y(i+1)modk​) 是由 (xi​,yi​) 通过上/下/左/右移动一次得来的（0≤i≤k−1），此时这 k 个格子就构成了一个「环」。如果另一个岛屿 B 所占据的格子全部位于这个「环」内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制运行

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

输出 #1复制运行

1
3

说明/提示

【样例说明】

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

01111
11001
10201
10001
11111

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

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

111111
100001
020301
100001
111111

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

【评测用例规模与约定】

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

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

蓝桥杯 2023 省赛 B 组 F 题。

只需要进行两次bfs即可

第一次bfs从数组再外面一层开始填充海水，往八个方向填充，用一个新数组存储填充情况，填充的位置设置为1，海水到不了的位置就为0，也就是一个0块为一个岛，且不需要考虑子岛情况 可以这么想如果存在环的话，这个环内部海水都进不去，直接就是将环包裹的所有格子都变成一个岛的

样例

0	1	1	1	1
1	1	0	0	1
1	0	1	0	1
1	0	0	0	1
1	1	1	1	1

新数组就变成

1	1	1	1	1	1	1
1	1	0	0	0	0	1
1	0	0	0	0	0	1
1	0	0	0	0	0	1
1	0	0	0	0	0	1
1	0	0	0	0	0	1
1	1	1	1	1	1	1

第二次bfs就是求这个新数组中有多少个岛咯

也就是求0块个数

bfs模板套就完事了 注意这里是往四个方向搜岛

ac代码

#include<bits/stdc++.h>
using namespace std;
int t,m,n;
string s;
int a[55][55],b[55][55],ans;
int c[4]={-1,0,1,0};
int d[4]={0,1,0,-1};
int x[8]={-1,-1,0,1,1,1,0,-1};
int y[8]={0,1,1,1,0,-1,-1,-1};
bool num[55][55],num1[55][55];
queue<pair<int,int>> q;
int main(){
    cin>>t;
    while(t--){
        cin>>m>>n;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(num,false,sizeof(num));
        memset(num1,false,sizeof(num1));
        ans=0;
        for(int i=1;i<=m;i++){
            cin>>s;
            for(int j=0;j<n;j++){
                a[i][j+1]=s[j]-'0';
            }
        }
        q.push({0,0});
        b[0][0]=1;
        num[0][0]=true;
        while(!q.empty()){
            auto t=q.front();
            for(int i=0;i<8;i++){
                t.first+=x[i];
                t.second+=y[i];
                if(t.first>=0&&t.first<=m+1&&t.second>=0&&t.second<=n+1&&a[t.first][t.second]==0&&!num[t.first][t.second]){
                    b[t.first][t.second]=1;
                    num[t.first][t.second]=true;
                    q.push({t.first,t.second});
                }
                t.first-=x[i];
                t.second-=y[i];
            }
            q.pop();
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(b[i][j]==0&&!num1[i][j]){
                    q.push({i,j});
                    num1[i][j]=true;
                    while(!q.empty()){
                        auto t=q.front();
                        for(int k=0;k<4;k++){
                            t.first+=c[k];
                            t.second+=d[k];
                            if(t.first>0&&t.first<=m&&t.second>0&&t.second<=n&&b[t.first][t.second]==0&&!num1[t.first][t.second]){
                                num1[t.first][t.second]=true;
                                q.push({t.first,t.second});
                            }
                            t.first-=c[k];
                            t.second-=d[k];
                        }
                        q.pop();
                    }
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
}

新手 勿喷