解题思路各位爷来看数据,有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 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复