转载自:
https://blog.csdn.net/weixin_43914593/article/details/112851771
题目一看就是“连通块问题”,是基础搜索。用DFS或BFS都行:遍历一个连通块(找到这个连通块中所有的’#‘,并标记已经搜过,不用再搜);再遍历下一个连通块…;遍历完所有连通块,统计有多少个连通块。
回到题目,什么岛屿不会被完全淹没?若岛中有个陆地(称为高地),它周围都是陆地,那么这个岛不会被完全淹没。
用DFS或BFS搜出有多少个岛(连通块),并且在搜索时统计那些没有高地的岛(连通块)的数量,就是答案。
因为每个像素点只用搜一次且必须搜一次,所以复杂度是$O(n^2)$的,不可能更好了。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
vis[x][y] = 1; //标记这个'#'被搜过。注意为什么可以放在这里
if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
flag = 1; //上下左右都是陆地,不会淹没
for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
int nx = x + d[i][0], ny = y + d[i][1];
//if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水,所以不用这么写了
if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地,目的是标记它们
dfs(nx,ny);
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
int ans = 0 ;
for(int i = 1; i <= n; i++) //DFS所有像素点
for(int j = 1; j <= n; j++)
if(a[i][j]=='#' && vis[i][j]==0){
flag = 0;
dfs(i,j);
if(flag == 0) //这个岛全部被淹
ans++; //统计岛的数量
}
cout<<ans<<endl;
return 0;
}
wow,好牛,写写看,等等,怎么判断的呢,嗯,四面皆有,嗯,等等,边上角上呢?没有考虑边界哦(笑
画面感十足
为什么不会超时呢兄弟
我还在想为什么没有判断边界,结果发现题目要求第一行和列与第n行和列都是海,判断岛周围不会有越界情况
妙啊,我还傻傻的去染色之后再统计 再相减
大佬能接受一下这里什么意思嘛int nx = x + d[i][0], ny = y + d[i][1]
向上下左右移动
tql orz
666666
考不考虑环形岛呢,就是那种中间被海水渗透,然后崩裂出很多岛屿
一生二,二生三,三生无数小岛屿
有点道理
那样岛屿只会变多 不会变少 题目要求的是 淹没的岛屿
参考数据如下
if(a[x][y+1]==’#’ && a[x][y-1]==’#’ && a[x+1][y]==’#’ && a[x-1][y]==’#’)
flag = 1; //上下左右都是陆地,不会淹没
佬请问这里是不是和题目的陆地定义不太一样呢? 以左上角的’#’坐标为(x,y)为例,样例中(x,y)、(x+1,y)、(x,y+1)、(x+1,y+1)是一块陆地 是一个井字形 可是上面的代码里面陆地的定义是十字形为啥呀?
十字型说明中间那块地不会沉没,那么这块岛屿就是不会沉没的岛。样例中的井字型属于会沉没的岛屿。
赞!是我想得太复杂了
一看就懂,一写就跪
芜湖, 和我自己想的写的一样
牛
感觉这道题dfs 和bfs很像
妙啊
很不粗的 dfs !