当前位置：首页 > web >正文

[蓝桥杯]全球变暖

web 2025/6/28 1:03:28

全球变暖

题目描述

你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

....#..

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述

第一行包含一个整数 N (1≤N≤1000)N (1≤N≤1000)。

以下 NN 行 NN 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 NN 行、第 NN 列的像素都是海洋。、

输出一个整数表示答案。

输入输出样例

示例

输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 13594 | 总提交次数: 16617 | 通过率: 81.8%

难度: 困难标签: 2018, 省赛, DFS

算法思路

题目要求统计被完全淹没的岛屿数量。核心思路是通过DFS/BFS遍历每个岛屿，在遍历过程中记录：

岛屿总陆地数：连通块中#的数量
会被淹没的陆地数：至少有一面邻接海洋的#数量
若两者相等，则该岛屿会被完全淹没

算法演示代码实现

#include <iostream>
#include <queue>
using namespace std;typedef pair<int, int> PII;
const int N = 1010;
int n;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};void bfs(int x, int y, int &total, int &bound) {queue<PII> q;q.push({x, y});st[x][y] = true;while (!q.empty()) {auto t = q.front();q.pop();total++;bool is_bound = false;for (int i = 0; i < 4; i++) {int nx = t.first + dx[i], ny = t.second + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;if (g[nx][ny] == '.') {is_bound = true;continue;}if (!st[nx][ny]) {st[nx][ny] = true;q.push({nx, ny});}}if (is_bound) bound++;}
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> g[i];int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (g[i][j] == '#' && !st[i][j]) {int total = 0, bound = 0;bfs(i, j, total, bound);if (total == bound) cnt++;}}}cout << cnt << endl;return 0;
}

代码解析

数据结构：
- g[][]：存储海域地图
- st[][]：标记访问状态
- dx/dy：方向数组（上右下左）
BFS核心逻辑：
- 总陆地数：每访问一个#，total++
- 淹没判断：检查四周是否有海洋，有则bound++
- 队列操作：将未访问的相邻陆地加入队列
主函数流程：
1. 读取输入数据
2. 遍历每个像素点
3. 对未访问的#启动BFS
4. 判断是否完全淹没（total == bound）

实例验证

输入：

7
.......
.##....
.##....
....##.
..####.
...###.
.......

执行过程：

发现左上岛屿(1,1)：
- 总陆地数：4
- 会被淹没数：4（所有陆地邻接海洋）
- 完全淹没计数+1
发现右下岛屿(3,4)：
- 总陆地数：6
- 会被淹没数：4（中心2块陆地不邻接海洋）
- 不计入淹没

输出：1

注意事项

边界处理：
- 使用nx >= n而非nx > n（索引从0开始）
- 题目保证边界都是海洋，无需特殊处理
访问标记：
- 必须在入队时标记st[nx][ny]=true
- 避免重复访问导致死循环
方向数组：
- 确保4个方向（上右下左）
- 顺序不影响结果但影响遍历顺序

测试点设计

测试类型	输入特点	验证重点
最小规模	N=3，单个岛屿	基础功能
全海洋	所有像素为`.`	输出0
全陆地	所有像素为`#`	中心不被淹没
最大规模	N=1000	时间限制1s
复杂岛屿	环形/镂空岛屿	淹没判断准确性
边界岛屿	岛屿贴边（题目保证边界为海）	自动淹没

优化建议

DFS替代BFS：

void dfs(int x, int y, int &total, int &bound) {st[x][y] = true;total++;bool is_bound = false;for(int i=0; i<4; i++){int nx = x+dx[i], ny = y+dy[i];if(nx<0||nx>=n||ny<0||ny>=n) continue;if(g[nx][ny]=='.') is_bound = true;else if(!st[nx][ny]) dfs(nx, ny, total, bound);}if(is_bound) bound++;
}

优势：减少队列操作，代码更简洁

内存优化：
- 复用g[][]数组：将访问过的#改为0，省去st[][]空间
- 方向数组改为静态常量：static const int dx[] = {...}
性能优化：
```
// 提前终止条件
if (bound > 0 && total - bound == 0) return; // 已确定完全淹没
```
适用场景：当岛屿很大且早期确定不会被完全淹没时
并行计算：
```
#pragma omp parallel for
for (int i=0; i<n; i++) {// 各列独立处理
}
```
优势：N=1000时加速明显（需确保线程安全）