指针原来是套娃的


私信TA

用户名:uq_92467646842

访问量:9779

签 名:

数学改变科学,科学改变世界

等  级
排  名 19
经  验 14516
参赛次数 40
文章发表 96
年  龄 0
在职情况 学生
学  校
专  业 物联网工程

  自我简介:

QQ:2830671713

解题思路:

做这道题看错了两个地方,一开始做成了求存活的#的数量,后来又看成了存活的岛屿的数量,其实题目问的是有多少岛屿被淹没。

可以上下左右联通的为同一岛屿,以样例数据为例:

image.png

有两岛屿,只有右下角的岛屿中有一个不和海洋接触的陆地#,所以左上角的岛屿会被淹没,右下角的岛屿会存留下来。

所以问题转变成了将这些岛屿找出来,并且查找岛屿内有没有不和海洋连接的陆地,如果没有的就看成被淹没,答案数量+1。

先遍历数组,如果找到了陆地#,而且没有被标记过(不是之前岛屿里的陆地),就从这个陆地开始向上下左右四个方向寻找,将找到陆地进行标记,在下一次寻找的时候不查找标记过的陆地#。

同时记录一个陆地上下左右是不是都是陆地,如果找遍联通的陆地都没有(说明这个岛屿会被淹没),就返回一个0,让答案数+1。

上面的情况用dfs bfs都可以做,不过bfs在做判断上更简单一些。


参考代码:

#include <bits/stdc++.h>
#include <queue>
using namespace std;

struct node{
	int x,y,l;//坐标xy,l记录走过的步数,不过在这道题里没有用
};

int dx[8]={1,-1,0,0,-1,1,1,-1};//上 下 左 右 右上 右下 左下 左上 
int dy[8]={0,0,-1,1,1,1,-1,-1};//四个方向寻找就可以了

bool vis[1001][1001];//记录是否访问过
char p[1001][1001];
queue<node>q;
int n,z=0;

bool dfs(int x1,int y1){
	bool b=0;
	q.push({x1,y1,1});//坐标入队,从x1 y1开始寻找
	while(!q.empty()){
		int k=0;//记录周围有多少个陆地
		node now=q.front();
		vis[now.x][now.y]=1;
		q.pop();
		for(int i=0;i<4;i++){//四个方向寻找
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>0&&y>0&&x<=n&&y<=n){
				if(p[x][y]=='#'){//如果是陆地
					k++;
					if(!vis[x][y]){//如果没有访问过
						vis[x][y]=1;
						q.push({x,y,now.l+1});
					}
				}
			}	
		}
		if(k==4)b=1;//如果上下左右都是陆地
	}
	return b;//返回岛屿是否没有被淹没

}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>p[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[i][j]==0&&p[i][j]=='#'){//如果没有访问过并且是陆地
				if(!dfs(i,j))z++;//如果这个岛屿会被淹没,答案+1
			}
		}
	}
	
	cout<<z;

 	return 0;
}


 

0.0分

4 人评分

  评论区