BISHI80. 走迷宫
题目描述
给定一个 n 行 m 列的网格。你从起点 s 出发，每一次可以向上、下、左、右 移动一步（不超出边界）。某些格子上存在障碍物，无法经过。 求从 s 移动到终点 t 的最少步数；若无法到达，输出 -1。
输入格式
第一行输入两个整数 n、m，代表网格的行数与列数。
第二行输入四个整数 x1、y1、x2、y2，代表起点与终点的坐标（行列均从 1 开始）。
此后 n 行，第 i 行输入一个长度为 m 的字符串：* 表示障碍物，. 表示可通行。
保证起点所在格子可通行。
输出格式
输出一个整数，表示最少移动次数；若无法到达，输出 -1。
示例
示例 1
输入：
5 5
1 1 5 5
.....
****.
.....
**.**
.....
输出：
12
说明： 第 2 行只有第 5 列可通行、第 4 行只有第 3 列可通行， 必须绕行，最短需要 12 步。
示例 2
输入：
5 5
1 1 4 5
.....
****.
.....
**.**
.....
输出：
-1
说明： 终点 (4,5) 被障碍物隔开，无法到达。
示例 3
输入：
5 5
1 1 5 5
.....
****.
.....
*****
.....
输出：
-1
说明： 第 4 行整行是障碍物，把上下完全隔断。
解题思路
第一步：理解问题本质
网格里每一步的代价都是 1，这是典型的无权图最短路。 无权图最短路的标准算法就是 BFS —— 按层扩散，第一次到达某点的层数 就是它到起点的最短距离。
第二步：用 DFS 找最短路（不推荐）
DFS 也能枚举所有路径并取最小值，但需要遍历全部路径， 复杂度会退化到指数级，且要额外维护最小值，容易出错。
第三步：BFS（推荐）
- 用
dist数组同时承担两个职责：是否访问过（-1 表示没访问） 和到起点的距离。 - 起点
dist[sx][sy] = 0并入队。 - 每次出队，向四方向扩展：若下一格在界内、可通行、且
dist仍为 -1， 则dist[下一格] = dist[当前] + 1并入队。 - 最后输出
dist[tx][ty]：若终点从未被访问，它天然是 -1， 正好就是题目要求的「无法到达」。
把「是否访问」和「距离」合并进一个数组，是网格 BFS 的常见小技巧。
完整代码实现
算法可视化 · 逐帧回放这道题的代码280 帧 · 录制输入
import sys
from collections import deque
def solve() -> None:
"""BFS 求网格最短步数"""
data = sys.stdin.read().split()
if not data:
return
idx = 0
n = int(data[idx]); m = int(data[idx + 1]); idx += 2
x1 = int(data[idx]); y1 = int(data[idx + 1])
x2 = int(data[idx + 2]); y2 = int(data[idx + 3]); idx += 4
grid = data[idx:idx + n]
sx, sy = x1 - 1, y1 - 1 # 题目坐标从 1 开始，转成 0 开始
tx, ty = x2 - 1, y2 - 1
dist = [[-1] * m for _ in range(n)]
dist[sx][sy] = 0
queue = deque([(sx, sy)])
while queue:
x, y = queue.popleft()
if x == tx and y == ty:
break
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 dist[nx][ny] == -1 and grid[nx][ny] == '.':
dist[nx][ny] = dist[x][y] + 1
queue.append((nx, ny))
sys.stdout.write(str(dist[tx][ty]) + "\n")
if __name__ == "__main__":
solve()
示例推演
以示例 1 的网格（1 起坐标）为例：
行1: . . . . .
行2: * * * * .
行3: . . . . .
行4: * * . * *
行5: . . . . .
因为行 2 只有第 5 列通、行 4 只有第 3 列通，路径被「挤」成：
| 段 | 路径 | 步数 |
|---|---|---|
| 行1 向右到第 5 列 | (1,1)→…→(1,5) | 4 |
| 下行经过行2、行3 的第 5 列 | (2,5) | 1 |
| 行3 内向左到第 3 列 | (3,4)→(3,3) | 2 |
| 下行到行4、行5 第 3 列 | (4,3)→(5,3) | 2 |
| 行5 向右到第 5 列 | (5,4)→(5,5) | 2 |
| 其余 | (3,5) 是行2→行3 的一步 | 1 |
合计 4 + 1 + 1 + 2 + 2 + 2 = 12，与答案一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| DFS 枚举所有路径 | 指数级 | O(n*m) | 不推荐 |
| BFS | O(n*m) | O(n*m) | 推荐 |
易错点总结
1. 坐标从 1 开始
输入坐标是行列都从 1 计数，读入后一定要 -1 转成 0 起点，
否则会整体偏移一行一列。
2. dist 初值用 -1 而不是 0
如果初值设成 0，「没访问」和「距离为 0」就分不清了。 用 -1 表示未访问，顺便让「不可达」直接输出 -1。
3. 障碍物符号是 * 不是 #
本题用 * 表示障碍，判断时别习惯性写成 #。
扩展思考
- 如果每次移动代价不同（有的格子走起来更贵），就换成 Dijkstra。
- 多源最短路（多个起点）只需在初始化时把所有起点都入队。