解题思路各位爷来看数据,有50个,那就开52样例,这样的目的是为了把外岛全部用0也就是海水包围起来,才能在0,0遍历时全部将外岛的1感染成2,就像这样

0000000

0011110

0110010

0101010

0100010

0111110

0000000

开俩数组,将数据都日进去,将A数组里的外岛感染成2后双FOR遍历图,将没变2的1也就是内岛屿的那个位置找出来,将A数组里那个位置的1变成B数组的0;毕竟内岛和0毫无区别,然后在DFS一次将岛屿个数数出来就可以了
注意事项:

参考代码:

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int m,n;

int ddx[8]={0,0,-1,1,1,1,-1,-1},ddy[8]={-1,1,0,0,-1,1,-1,1};

int a[52][52],b[52][52];

void color(int p,int q){

    if(a[p][q]==1){

        a[p][q]=2;

        return;

    }

    if(p<0||p>m+1||q<0||q>n+1||a[p][q]){

        return;

    }

    a[p][q]=2;

    for(int i=0;i<8;i++)color(p+ddx[i],q+ddy[i]);

}

void dfs1(int i,int j){

    if (i < 1 || i > m  || j < 1 || j > n  || b[i][j] != 1) {

        return;

    }

    b[i][j] = 0;

    dfs1(i + 1, j);

    dfs1(i - 1, j);

    dfs1(i, j + 1);

    dfs1(i, j - 1);

}

void solve()

{

    int ans=0;

    cin>>m>>n;

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    for(int i=1;i<=m;i++){

        string str;

        cin>>str;

        for(int j=1;j<=n;j++)

        {

            if(str[j-1]=='1')a[i][j]=1;

            b[i][j]=a[i][j];

        }

    }

    color(0,0);

    for(int i=1;i<=m;i++){

        for(int j=1;j<=n;j++){

            if(a[i][j]==1)b[i][j]=0;

        }

    }

    

    for(int i=1;i<=m;i++){

        for(int j=1;j<=n;j++){

            if(b[i][j]==1)

            {

                dfs1(i,j);

                ans++;

            }   

            

        }

    }

    cout<<ans<<endl;

}

signed main() {

    int t;

    cin >> t;

    while (t--){

    solve();

    }

    return 0;

}


点赞(0)
 

0.0分

2 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论