[第十四届蓝桥杯省B 岛屿个数]

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

在岛屿 A 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列: ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x_0,y_0),(x_1,y_1),...,(x_{k−1},y_{k−1}) (x0,y0),(x1,y1),...,(xk1,yk1),其中 (xi+1%k ,yi+1 % k) 是由
( x i , y i ) (x_i,y_i) (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。

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

数据范围
对于 30% 的评测用例,1≤M,N≤10。
对于 100% 的评测用例,1≤T≤10,1≤M,N≤50。

输入样例:

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

输出样例:

1
3

样例解释
对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:

01111
11001
10201
10001
11111

岛屿 2 在岛屿 1 的 “环” 内部,所以岛屿 2 是岛屿 1 的子岛屿,答案为 1。

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

111111
100001
020301
100001
111111

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

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=15;
typedef pair<int,int> PII; 
int a,b;
int g[N][N];
bool vis1[N][N],vis2[N][N];
//g陆地,vis1宽搜标记,vis2检查是否成环标记 

void dfs(int x,int y){
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    vis1[x][y]=true;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<1||nx>a||ny<1||ny>b||vis1[nx][ny]||g[nx][ny]==0) continue;
        dfs(nx,ny);
    }
} 

bool check(int x,int y){
    int dx[8]={1,0,-1,0,1,1,-1,-1};
    int dy[8]={0,1,0,-1,1,-1,1,-1};
    for(int i=0;i<8;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(g[nx][ny]||vis2[nx][ny]) continue;
        if(nx<1||nx>a||ny<1||ny>b) return true;
        vis2[nx][ny]=1;
        if(check(nx,ny)) return true;
    }
    return false;
}

int main () {
    int n;
    cin>>n;
    while(n--){
        memset(g,0,sizeof g);
        memset(vis1,0,sizeof vis1);
        memset(vis2,0,sizeof vis2);
        
        cin>>a>>b;
        for(int i=1;i<=a;i++)
            for(int j=1;j<=b;j++){
                char x;cin>>x;
                g[i][j]=x-'0';
            }
            
        int res=0;
        for(int i=1;i<=a;i++)
            for(int j=1;j<=b;j++){
                if(g[i][j]&&vis1[i][j]==0){
                    vis1[i][j]=1;
                    dfs(i,j);
                    memset(vis2,0,sizeof vis2);
                    vis2[i][j]=1;
                    if(check(i,j)) res++;
                }
            }
        cout<<res<<endl;    
    }
    
    return 0;
}

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐