题目
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
1
一、思路:
如果一个岛屿(#)的它的上下左右都是#,那么与它相连的岛屿就不会被淹没,否则就会被淹没。(使用此方法可以杜绝,淹没后又产生新岛屿的情况)
代码思路:使用bfs遍历二维数组(地图):把当前元素入队,获取其x和y的坐标,然后把它出队,如果它没有被遍历过且它是岛屿,则判断它的上下左右是否都是#(标记为已遍历过),如果是,则标记这块岛屿不会被淹没,把位移后与它相邻的且没有遍历过的岛屿,入队列,继续遍历。当队列为空时,返回;
如果这块岛屿不会被淹没,则不会被淹没的岛屿数加1。
二、源代码
#pragma once
#include<iostream>
#include<queue>
#include<string>
using namespace std;
/**
第九届蓝桥杯 全球变暖 bfs
*/
//初始化最大值
const int maxn = 1005;
//矩阵的行列数
int n = 0;
//初始化地图
char mp[maxn][maxn];
//判断是否遍历过
bool mp_type[maxn][maxn] = { false };
//方向,分别是左,下,上,右
int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };
struct Point
{
int x;
int y;
Point(int _x, int _y) : x(_x), y(_y) {};
};
bool bfs1(int x, int y) {
//定义队列
queue<Point> q;
//x,y入队
q.push(Point(x, y));
//初始化flag
bool flag = false;
//队列不空执行循环
while (!empty(q))
{
//获取首个端点
Point p = q.front();
//获取信息的成员出队
q.pop();
//初始化其周边陆地个数
int cnt = 0;
//遍历其周边陆地
for (int i = 0; i < 4; ++i) {
//原坐标加上位移算出新的位置
int dx = p.x + dir[i][0];
int dy = p.y + dir[i][1];
//判断是否越界
if (dx < 0 || dx >= n || dy < 0 || dy >= n)
continue;
//判断周围陆地
if (mp[dx][dy] == '#') {
//有一个陆地,陆地数+1
cnt++;
if (!mp_type[dx][dy]) {
//如果位移后的陆地未遍历过,
//将其标记,并入队
mp_type[dx][dy] = true;
q.push(Point(dx, dy));
}
}
if (cnt == 4) {
//则周围都是陆地不会被淹没
flag = true;
}
}
}
//进行遍历
return flag;
}
class daoyu2
{
public :
void run() {
int ans = 0;
scanf_s("%d", &n);
//存储地图
for (int i = 0; i < n; i++) {
cin >> mp[i];
}
//遍历bfs;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mp[i][j] == '#' && !mp_type[i][j]) {
mp_type[i][j] = true;
if (!bfs1(i, j))
ans++;
}
}
}
cout << ans;
}
};
三、个人体会
通过队列来实现对连接陆地的整体标记避免重复标记,这是第一个做的bfs的题,还不能通过自己的想法来写出来,不过看了几道bfs的题之后,发现思路大同小异,有一个整体的框架,之后再总结出来。