BISHI82. 没挡住洪水
题目描述
吴铭市洪水肆虐，市政部门临时砌起的围墙是豆腐渣工程，被洪水冲毁，
只留下用 # 表示的空地。地图是一个 N×N 的字符矩阵：. 表示已经被洪水
淹没的区域，# 表示空地。四联通的 # 组成一个区域。
洪水还会继续上涨：所有与「已经被洪水淹没的区域」上下左右相邻的空地格子， 都会在这一次上涨中被淹没。请计算此次上涨后，有多少个空地区域会被 完全淹没。
输入格式
第一行输入整数 N。
随后 N 行，每行 N 个字符，构成地图，只含 . 与 #。
已知边界四条边全部是已经被洪水淹没的区域。
输出格式
输出一个整数，表示一天后会完全消失的空地区域数量。
示例
示例 1
输入：
1
.
输出：
0
说明： 地图全是水，没有任何空地区域，答案为 0。
解题思路
第一步：理解问题本质
「一个区域被完全淹没」当且仅当：它的每一个格子都与洪水相邻。
原因在于洪水这次只涨一层 —— 只有与「已淹没区域」上下左右相邻的空地
才会进水。如果区域内存在一个格子，它的上下左右全是 #（也就是被同区域
的格子包围），那它这次就不会进水，区域自然没有被完全淹没。
第二步：暴力做法
枚举每个 #，判断它这次是否会被淹没；然后枚举所有四联通区域，
看区域里是否所有格子都会被淹没。逻辑上正确，但要反复扫描地图，
实现容易写得混乱。
第三步：BFS 找连通块 + 逐格判断（推荐）
一次遍历即可完成：
- 对每个 尚未访问 的
#，启动一次 BFS/DFS，收集整个四联通区域； - 在扩散的同时，检查每个格子的四个方向：
只要有任意一个方向是
.（或越界），就说明这个格子临水、这次会被淹没； - 给区域打一个标记
every_cell_touches_water： 只要遇到一个格子四邻全是#（不临水），就把它置为False； - 遍历完该区域后，若标记仍为
True，答案 +1。
「找连通块」和「判断是否临水」可以在同一次 BFS 里做完， 不需要开两遍地图。
完整代码实现
算法可视化 · 逐帧回放这道题的代码10 帧 · 录制输入
import sys
from collections import deque
def solve() -> None:
"""统计每个 '#' 区域是否每个格子都临水，输出完全淹没的区域数"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
grid = data[1:1 + n]
seen = [[False] * n for _ in range(n)]
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
fully_submerged = 0
for i in range(n):
for j in range(n):
if grid[i][j] != '#' or seen[i][j]:
continue
# 找到一个新区域，BFS 收集它所有格子
seen[i][j] = True
queue = deque([(i, j)])
every_cell_touches_water = True
while queue:
x, y = queue.popleft()
touches_water = False
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < n and 0 <= ny < n):
touches_water = True # 出界也算临水
elif grid[nx][ny] == '.':
touches_water = True
elif not seen[nx][ny]:
seen[nx][ny] = True
queue.append((nx, ny))
if not touches_water:
every_cell_touches_water = False
if every_cell_touches_water:
fully_submerged += 1
sys.stdout.write(str(fully_submerged) + "\n")
if __name__ == "__main__":
solve()
示例推演
以一个 5×5 的迷宫为例：
. . . . .
. # . # .
. . . . .
. . . . .
. . . . .
两个孤立的 # 各自成区域。坐标 (2,2) 的 # 四个方向都是 .，
临水 → 被淹没；坐标 (2,4) 的 # 同样临水 → 被淹没。
两个区域都被完全淹没，答案是 2。
再换成一个 3×3 的实心块：
. . . . .
. # # # .
. # # # .
. # # # .
. . . . .
四个角上的 # 临水，但中心格 (3,3) 的上下左右全是 #，不临水，
所以这个区域没有被完全淹没，答案为 0 —— 这正是本题的关键：
「有格子被围在里面」就说明洪水这次淹不透它。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 反复扫描地图 | O(N^4) 量级 | O(N^2) | 不推荐 |
| BFS 连通块 + 逐格判断 | O(N^2) | O(N^2) | 推荐，每个格子只访问一次 |
易错点总结
1. 把「区域临水」当成「区域被完全淹没」
区域只要挨着洪水就会被部分淹没；要「完全」淹没， 必须每一个格子都临水。少判断一个格子就会多算。
2. 越界方向的处理
题目保证边界四条边是水，所以 # 不会出现在边界上。
但在代码里把越界也算作「临水」更安全，不会误判。
3. 标记数组的时机
同一个区域可能被多次扫到，必须在入队时就标记 seen，
否则一个连通块会被重复 BFS，答案翻倍。
扩展思考
- 如果问的是「这次上涨后还剩多少个空地区域没被淹」，
只需统计
every_cell_touches_water为False的区域数。 - 如果洪水可以持续上涨（多层），那么任何与外界连通的区域最终都会被淹没， 问题就退化成「统计包围起来的区域」，是另一个经典题。