BISHI76. 迷宫寻路
题目描述
旺仔哥哥被困在一个 n 行 m 列的矩形迷宫里。每个格子要么是空地（.），
要么是墙（#）。他只能从一个空地移动到其上下左右相邻的空地。
已知起点为左上角 (1, 1)，终点为右下角 (n, m)。请判断他是否能到达终点。
输入格式
第一行输入两个正整数 n、m。
接下来的 n 行，每行输入一个长为 m 的、仅包含字符 . 与 # 的字符串，
描述整个迷宫。保证起点和终点均为空地。
输出格式
若旺仔哥哥可以走到终点，则输出单词 Yes；否则输出 No。
示例
示例 1
输入：
3 5
.##.#
.#...
...#.
输出：
Yes
说明：
存在一条只经过 . 的路径从 (1,1) 到 (3,5)，例如
(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(1,3)→(1,4)→(1,5)→(2,5)→(3,5)。
解题思路
第一步：理解问题本质
把每个 . 当成图上的一个点，两个上下左右相邻的空地之间有一条边。
问题就是：图中起点和终点是否连通？这是一次标准的图遍历。
第二步：暴力 DFS（可能爆栈）
从起点出发递归搜索：
def dfs(x, y):
if 越界 or 是墙 or 已访问:
return
mark(x, y)
dfs(x + 1, y); dfs(x - 1, y); dfs(x, y + 1); dfs(x, y - 1)
思路没问题，但递归深度可能达到 n×m（最坏上百万），
Python 默认递归限制会直接 RecursionError。
即使提高上限，栈空间也可能不够。
第三步：BFS（推荐）
用队列代替递归，一层一层往外扩散，天然不会爆栈：
- 把起点入队并标记已访问；
- 每次取出队首，向四个方向找没访问过的空地，标记后入队；
- 一旦访问到终点就输出
Yes； - 队列空了还没到终点，输出
No。
BFS 还能顺带得到「最短步数」，是多源网格题的首选写法。
完整代码实现
算法可视化 · 逐帧回放这道题的代码170 帧 · 录制输入
import sys
from collections import deque
def solve() -> None:
"""从左上角 BFS，判断能否到达右下角"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
m = int(data[1])
grid = data[2:2 + n]
if grid[0][0] == '#' or grid[n - 1][m - 1] == '#':
sys.stdout.write("No\n")
return
seen = [[False] * m for _ in range(n)]
seen[0][0] = True
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
if x == n - 1 and y == m - 1:
sys.stdout.write("Yes\n")
return
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and not seen[nx][ny] and grid[nx][ny] == '.':
seen[nx][ny] = True
queue.append((nx, ny))
sys.stdout.write("No\n")
if __name__ == "__main__":
solve()
示例推演
迷宫如下（. 可走，# 是墙）：
. # # . #
. # . . .
. . . # .
从 (1,1) 出发，BFS 队列的扩散过程（坐标为 1 起）：
| 层 | 队列中的格子 | 说明 |
|---|---|---|
| 0 | (1,1) | 起点入队 |
| 1 | (1,1)→出队，入队 (2,1) | 向下可走 |
| 2 | (2,1)→(3,1) | |
| 3 | (3,1)→(3,2) | 向右 |
| 4 | (3,2)→(3,3) | |
| 5 | (3,3)→(2,3) | 向上 |
| 6 | (2,3)→(1,3)、(2,4) | |
| … | 继续扩散到 (1,5)、(2,5)、(3,5) | 到达终点 → Yes |
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归 DFS | O(n*m) | O(n*m) | 可能爆栈 |
| 迭代 DFS | O(n*m) | O(n*m) | 安全 |
| BFS | O(n*m) | O(n*m) | 推荐，还能求最短路 |
易错点总结
1. 忘记标记已访问
如果只在出队时标记，同一个格子可能被重复入队，队列爆炸（甚至死循环）。 入队时就标记是标准做法。
2. 起终点就是墙
虽然题面保证起点终点是空地，但加上一句判断更稳健；
若不判断而终点是墙，BFS 会正常输出 No，起点是墙则可能误判为可达。
3. 坐标与字符数组的下标
grid[i][j] 中 i 是行、j 是列；题目坐标 (1,1) 对应 grid[0][0]。
扩展思考
- 若要求「最短路径长度」，BFS 的层数就是答案（见 BISHI80）。
- 若还要求输出一条路径，需要额外记录每个格子的前驱。