ripper


私信TA

用户名:dotcpp0714804

访问量:408

签 名:

海的那边是自由嘛

等  级
排  名 16373
经  验 764
参赛次数 0
文章发表 6
年  龄 0
在职情况 学生
学  校 兰州师专
专  业

  自我简介:

膜拜各位爷

解题思路各位爷来看数据,有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分

2 人评分

看不懂代码?想转换其他语言的代码? 或者想问其他问题? 试试问问AI编程助手,随时响应你的问题:

编程语言转换

万能编程问答  

代码解释器

代码纠错

SQL生成与解释

  评论区