LeetCode 505. 迷宫 II
目录
题目描述
题意分析
迷宫是一张 0 表示空地、1 表示墙的网格。球从起点出发，每次只能选一个方向，然后一直滚到撞墙或撞到边界才停下，中途不能主动刹车。要求返回从起点滚到终点所经过的最少空地格数，无法停在终点就返回 -1。
「不能中途停」这一条彻底改变了问题的性质：球在滚动途中经过的格子并不是可选的落脚点，只有撞墙前的最后一格才算一个真正的状态。所以相邻状态之间的距离不是 1，而是这一段滚动的长度。
计数口径要看清：题目数的是「经过的空地格数」，也就是滚动的格子数，起点本身不计入。终点必须是球停下来的位置，路过终点但没停下不算到达。
边界情况有几处：起点就是终点时答案为 0；球在某个方向上贴着墙，一格也滚不动，这个方向不产生任何新状态；终点可能在一条通道的中间，球只能路过无法停留，这时应当返回 -1。
解法：线性 Dijkstra + 滚动模拟
核心思路
先看能不能沿用普通的网格广度优先搜索。不能——广度优先搜索给出最短路的前提是每条边权重相同，而这里一次滚动的代价是可变的：可能滚 1 格，也可能滚 10 格。用它会得到「滚动次数最少」的路径，而不是「格子数最少」的路径。
正确的建模是把问题抽象成带权图：节点是所有可以停下来的格子，一条边表示从某个停点朝某个方向滚到下一个停点，边权就是这次滚动经过的格数。这样问题就变成了标准的单源最短路，而且边权全为非负整数，Dijkstra 适用。
Dijkstra 维持的不变量是：每一轮从尚未定型的节点中挑出当前距离最小的那个，它的距离此刻就已是最终值。这一点靠边权非负保证——任何绕道经过其他未定型节点的路径，长度都不会比它当前的值更小。定型之后再用它去松弛四个方向的邻居。
实现上不必手写二叉堆。网格总共只有 $m \cdot n$ 个节点，每轮线性扫描一遍找最小值，总代价是节点数的平方，在题目给定的网格规模下完全够用，代码也短得多，白板上不容易写错。距离数组用一个足够大的哨兵表示不可达，最后判断终点是否仍是哨兵即可。
解题步骤
- 把距离矩阵全部填成哨兵大值，起点置 0。哨兵要选得比任何真实路径都大，但又不能大到与步数相加时溢出，所以取整型上界的四分之一或按网格规模算一个上界，而不是直接用整型最大值。
- 循环最多 $m \cdot n$ 轮，每轮全表扫描出「未定型且距离最小」的格子。找不到（说明剩下的全是不可达的哨兵）就提前退出，避免用哨兵距离去松弛出更离谱的值。
- 把选中的格子标记为已定型。这一步是 Dijkstra 的核心，标记之后它的距离不再改变，也不会被重复展开。
- 对四个方向各做一次滚动模拟：从当前格出发沿该方向一格一格试探，直到下一格越界或是墙才停，同时累计走过的格数。用「先算下一格、越界或撞墙就退出」的写法，退出时手里的坐标自然就是合法停点。
- 用「当前距离 + 本次滚动格数」去松弛停点。只有严格更小才更新，这样距离数组始终保存的是已发现路径中的最小值。注意贴墙时滚动格数为 0、停点就是自己，松弛条件自然不成立，不需要额外特判。
- 全部轮次结束后读终点距离，仍是哨兵说明球无法停在终点，返回 -1，否则返回该距离。
以
maze = [[0,0,0],[1,1,0],[0,0,0]]、start = [0,0]、destination = [2,0]走一遍：距离矩阵初始为全哨兵，dist[0][0] = 0。方向顺序取下、上、右、左。第一轮选中 (0,0)，距离 0，标记定型。向下：下一格 (1,0) 是墙，一格没滚，停点仍是 (0,0)，格数 0，松弛不成立。向上、向左都立刻越界，同样无效。向右：(0,1) 是空地、(0,2) 是空地、再往右越界，停在 (0,2)，格数 2，于是
dist[0][2] = 0 + 2 = 2。第二轮未定型格子里最小的是 (0,2)，距离 2，标记定型。向下：(1,2) 空地、(2,2) 空地、再往下越界，停在 (2,2)，格数 2，
dist[2][2] = 2 + 2 = 4。向左：滚回 (0,0)，格数 2，候选值 4 不小于 (0,0) 已定型的 0，不更新。向上、向右越界无效。第三轮选中 (2,2)，距离 4，标记定型。向左：(2,1)、(2,0)、再往左越界，停在 (2,0)，格数 2，
dist[2][0] = 4 + 2 = 6。向上滚回 (0,2)，候选值 6 不小于 2，不更新。向下、向右越界。第四轮选中 (2,0)，距离 6，标记定型。向上撞墙 (1,0) 滚不动；向右滚回 (2,2)，候选值 8 不小于 4；其余越界。
第五轮剩下的格子距离全是哨兵，扫描找不到有效最小值，循环提前退出。读
dist[2][0]得 6，即路径「右滚 2 格 → 下滚 2 格 → 左滚 2 格」，答案为 6。
代码实现
class Solution {
// 节点是可停靠的格子，边权是滚动步数。
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
int inf = Integer.MAX_VALUE / 4;
int[][] dist = new int[m][n];
boolean[][] used = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = inf;
}
}
dist[start[0]][start[1]] = 0;
int[] dx = new int[] {1, -1, 0, 0};
int[] dy = new int[] {0, 0, 1, -1};
for (int round = 0; round < m * n; round++) {
int bestX = -1;
int bestY = -1;
int bestDist = inf;
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (!used[x][y] && dist[x][y] < bestDist) {
bestDist = dist[x][y];
bestX = x;
bestY = y;
}
}
}
if (bestX == -1) {
break;
}
used[bestX][bestY] = true;
for (int d = 0; d < 4; d++) {
int nx = bestX;
int ny = bestY;
int step = 0;
while (true) {
int tx = nx + dx[d];
int ty = ny + dy[d];
if (tx < 0 || ty < 0 || tx >= m || ty >= n || maze[tx][ty] == 1) {
break;
}
nx = tx;
ny = ty;
step++;
}
int nd = dist[bestX][bestY] + step;
if (nd < dist[nx][ny]) {
dist[nx][ny] = nd;
}
}
}
int answer = dist[destination[0]][destination[1]];
if (answer >= inf) {
return -1;
}
return answer;
}
}
func shortestDistance(maze [][]int, start []int, destination []int) int {
// 节点是可停靠的格子，边权是滚动步数。
m := len(maze)
n := len(maze[0])
inf := m*n*(m+n) + 1
dist := make([][]int, m)
used := make([][]bool, m)
for i := 0; i < m; i++ {
dist[i] = make([]int, n)
used[i] = make([]bool, n)
for j := 0; j < n; j++ {
dist[i][j] = inf
}
}
dist[start[0]][start[1]] = 0
dx := []int{1, -1, 0, 0}
dy := []int{0, 0, 1, -1}
for round := 0; round < m*n; round++ {
bestX, bestY := -1, -1
best := inf
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if !used[x][y] && dist[x][y] < best {
best = dist[x][y]
bestX = x
bestY = y
}
}
}
if bestX == -1 {
break
}
used[bestX][bestY] = true
for d := 0; d < 4; d++ {
nx := bestX
ny := bestY
step := 0
for {
tx := nx + dx[d]
ty := ny + dy[d]
if tx < 0 || ty < 0 || tx >= m || ty >= n || maze[tx][ty] == 1 {
break
}
nx = tx
ny = ty
step++
}
next := dist[bestX][bestY] + step
if next < dist[nx][ny] {
dist[nx][ny] = next
}
}
}
answer := dist[destination[0]][destination[1]]
if answer >= inf {
return -1
}
return answer
}
复杂度分析
- 时间复杂度：$O((m \cdot n)^2)$，共至多 $m \cdot n$ 轮，每轮为了找当前最小距离要全表扫描 $m \cdot n$ 个格子；每轮内部的四次滚动模拟最多走过 $m + n$ 格，这一项被平方项吸收。
- 空间复杂度：$O(m \cdot n)$，距离矩阵和定型标记矩阵各占一份网格大小，滚动模拟本身只用常数个临时变量。
关键点总结
- 建图先于选算法。看清「一次移动的代价不固定」之后，节点和边的定义就自然浮出水面：节点是停点，边是一次完整滚动，边权是滚动格数。
- 边权是否相等决定了用广度优先搜索还是 Dijkstra。这条判据适用于所有网格最短路变体，是面试里最常被追问的一点。
- Dijkstra 的正确性依赖边权非负，其表现形式就是「每轮取出的最小距离节点可以立即定型」。能说清这一句，就说明你不是在背模板。
- 数据规模允许时，用线性扫描代替优先队列是白板上的实用取舍：把复杂度从 $O(mn \log mn)$ 放宽到 $O((mn)^2)$，换来的是十几行不会写错的代码。
- 哨兵值要选在「大于任何真实答案」和「加法不溢出」之间，直接用整型最大值会在松弛时溢出成负数。
- 面试视角：先主动说明为什么普通广度优先搜索不对，再给出建图方案，最后才谈实现选择。如果面试官追问网格很大怎么办，答「把线性扫描换成优先队列」即可，两者的算法骨架完全一致。
易错点总结
- 错误写法：直接套用四方向单步广度优先搜索。
maze = [[0,0,0],[1,1,0],[0,0,0]]、起点 (0,0)、终点 (2,0) → 得到的是滚动次数最少的方案，而题目要的是经过格数最少，两者的最优路径并不一定相同。- 错误写法：把边权当成 1（滚动一次记一步）。同一用例 → 返回 3（三次滚动），正确答案是 6（六个格子）。
- 错误写法：滚动时先移动再判断越界。球贴着上边界向上滚 → 读到下标 -1 直接抛出数组越界异常。
- 错误写法：把滚动途中经过的每个格子都当成可停靠节点入队。终点位于通道中间的迷宫 → 会返回一个正数，而正确答案是 -1，因为球根本停不下来。
- 错误写法：哨兵取
Integer.MAX_VALUE，松弛时直接算「哨兵 + 步数」。存在不可达区域的迷宫 → 加法溢出成负数，这个负值随后被当作最小距离选中，输出一个负数答案。- 错误写法：选中最小距离节点后不打定型标记，或者标记打在松弛之后。任意用例 → 同一个格子被反复选中，外层循环耗尽 $m \cdot n$ 轮却只处理了少数几个节点，远处的格子拿不到正确距离。
- 错误写法：扫描不到有效最小值时不提前退出，而是继续用哨兵距离松弛。含不可达区域的迷宫 → 不可达格子被赋上「哨兵 + 步数」这种伪距离，最后的可达性判断随之失效。
- 错误写法：起点等于终点时没走通用流程就返回 -1，或误以为必须至少滚动一次。
start与destination相同 → 应当返回 0，而不是 -1 或某个正数。- 错误写法：最后只判断终点距离是否等于哨兵。若中途发生过「哨兵 + 步数」的松弛，距离会变成比哨兵稍大的值，用等号判断会漏掉，应当用「大于等于哨兵」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 490. 迷宫 | 中等 | 同样的滚动模型，但只问可达性，无需带权最短路 |
| 499. 迷宫 III | 困难 | 在最短距离之上再按移动指令的字典序排序 |
| 743. 网络延迟时间 | 中等 | 显式邻接表上的裸 Dijkstra，答案取所有距离的最大值 |
| 778. 水位上升的泳池中游泳 | 困难 | 路径代价是沿途最大值而非求和，松弛式换成取较大者 |
| 1631. 最小体力消耗路径 | 中等 | 同为瓶颈路，也可用并查集按边权升序合并求解 |
| 787. K 站中转内最便宜的航班 | 中等 | 多出中转次数这一维约束，Dijkstra 的定型性质会失效 |
| 1334. 阈值距离内邻居最少的城市 | 中等 | 需要全源最短路，点数很小时直接上 Floyd 更省事 |