解题思路各位爷来看数据,有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语言代码)浏览:2339 |
点我有惊喜!你懂得!浏览:1435 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:555 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:644 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:570 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:623 |
C语言训练-求素数问题 (C语言代码)浏览:1458 |
蓝桥杯历届试题-九宫重排 (C++代码)浏览:2783 |
这可能是一个假的冒泡法浏览:991 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:592 |