LeetCode 499. 迷宫 III

2026-04-15 HGNULB 约 14 分钟

文章信息 6 个分类 11 个标签

分类

题目描述

✅ 499. 迷宫 III

题意分析

题目目标：小球放在 ball 位置，每次只能选一个方向让它滚，滚到撞墙或撞到边界才停，中途经过 hole 则掉进洞里立即停止。要求输出让球掉进洞的最短滚动距离对应的移动序列（u/d/l/r），距离相同时取字典序最小的序列；无法到达返回 "impossible"。

核心约束：两条约束决定了算法形态。第一，「一直滚到停」意味着相邻两个可停位置之间的距离不是 1 而是这一趟滚过的格数，边权非等值，普通 BFS 的层数不再等于距离。第二，除了距离还有第二关键字「路径字典序最小」，所以状态的比较必须是 (距离, 路径) 的二元组，而不是单看距离。

边界处理：球滚到洞里就停，不会滚过去，因此洞可能出现在某一趟的中途；起点本身可能贴着墙，某些方向 steps 为 0，这种「原地不动」的转移必须丢弃，否则会陷入自环；洞可能不可达，返回值是字符串 "impossible" 而不是空串。

实现取舍：距离和字典序两个关键字可以一起塞进优先队列的比较器，也可以先跑一遍纯距离最短路再回溯路径。前者代码短、一次成型，代价是队列元素带着字符串；后者省内存但要写两遍搜索。

解法：Dijkstra（距离最短 + 路径字典序最小）

核心思路

先想暴力：从起点开始 DFS，枚举每一步选哪个方向，记录走过的路径和累计距离，到洞时更新答案。问题是同一个停点会被无数条前缀重复展开，状态空间指数级爆炸，必须剪枝。

自然的下一步是 BFS。但 BFS 只在边权全为 1 时才保证「先出队的层数更小」，而这里一次滚动的代价是 1 到 $\max(m,n)$ 不等。举个例子：从起点向右滚 1 格到达 A，向下滚 5 格到达 B，BFS 会认为 A、B 同层，可实际距离差了 4，后续从 B 出发得到的结果会被错误地当成同样优。所以边权非等值 → 用 Dijkstra。

再看第二关键字。字典序比较有个很好的性质：如果两条路径的距离相同，那么它们在洞处的字典序大小，完全由各自的字符串决定，而字符串是沿路径前缀单调拼接的——给两条路径同时追加同一个方向字符，它们的相对大小不变。这条单调性正是 Dijkstra 成立的前提（松弛不会让已确定的最优解变差），所以可以直接把 (dist, path) 当成一个复合权重，用字典序作为 tie-break。

于是状态定义写死为：dist[x][y] = 从起点滚到停点 (x, y) 的最短滚动格数；bestPath[x][y] = 在 dist[x][y] 达到最小的前提下，字典序最小的移动序列。优先队列按 (dist, path) 升序弹出，弹出的第一个 (x, y) 状态即为该点的最终答案。

还有一条不变量必须守住：队列里可能残留过期状态。当某个点先被写入 ("ul", 6)、后又被更优的 ("lul", 6) 覆盖时，堆里那份 "ul" 还在。弹出时用 cur.dist == dist[x][y] && cur.path == bestPath[x][y] 双重校验，不匹配就丢弃——因为一个点的最优状态只有一份，用它继续扩展才不会污染后续。

最后是方向数组的写法：把四个方向按字符 d < l < r < u 的字典序排列。这不是必需的（比较器已经保证正确性），但它让「同距离时先探到的就是更小的路径」成为常态，减少了无谓的松弛更新。

解题步骤

第一步：初始化 dist 全为 INF、bestPath 全为空串，起点 dist = 0、路径为空串。 为什么用空串而不是 null：后面判断「该点是否被访问过」时统一用 isEmpty()，避免在比较字符串时踩空指针。

第二步：建一个按 (dist, path) 升序的最小堆，压入起点状态。 为什么比较器要两级：只比 dist 的话，同距离的多条路径出队顺序随机，先出队的会被当作最优并锁死，得不到字典序最小的那条。

第三步：弹出堆顶，先做过期校验，cur.dist != dist[x][y] || !cur.path.equals(bestPath[x][y]) 就 continue。 为什么：Dijkstra 的懒删除写法不从堆里移除旧状态，只能在出队时识别并跳过；不跳过就会用次优前缀去扩展，产生不满足不变量的结果。

第四步：对四个方向各模拟一次滚动。 内层 while 每次尝试走一格：越界或撞墙就停在上一格；否则前进并 steps++；前进之后立刻判断是否踩到洞，是则 break。为什么判洞要写在前进之后：球是滚到洞的格子上才掉下去的，先判后进会漏掉洞，先进后判才符合物理过程。

第五步：steps == 0 直接跳过该方向。 为什么：说明球紧贴着墙，这个方向根本推不动，落点还是自己。若不跳过，就会不断地把 (x, y) 以更长的路径重新入堆，形成死循环。

第六步：松弛。新距离 ndist = cur.dist + steps，新路径 npath = cur.path + 方向字符。当 ndist < dist[x][y]，或者 ndist == dist[x][y] 且 npath 字典序更小时，更新两张表并入堆。为什么同距离也要更新入堆：字典序更小的前缀会影响它后面所有的扩展结果，必须重新扩展一次。

第七步：堆空后返回 bestPath[hole]；若仍是空串说明从未被松弛到，返回 "impossible"。

以 maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]]、ball = [4,3]、hole = [0,1] 走一遍：方向按 d, l, r, u 顺序尝试。

起点 (4,3)，dist = 0，路径 ""。向 d 走出界，steps = 0 跳过。向 l：(4,2) 是空地，再往左 (4,1) 是墙，停在 (4,2)，steps = 1，得到状态 ((4,2), 1, "l")。向 r：(4,4) 后出界，停在 (4,4)，steps = 1，状态 ((4,4), 1, "r")。向 u：一路 (3,3) → (2,3) → (1,3) → (0,3) 后出界，steps = 4，状态 ((0,3), 4, "u")。堆内三个状态。

弹出 ((4,2), 1, "l")（距离 1，"l" 比 "r" 小）。向 l 立刻撞墙 steps = 0 跳过；向 r 滚回 (4,4) 得 dist = 3，但 dist[4][4] 已是 1，不更新；向 u 一路滚到 (0,2)，steps = 4，dist = 5，路径 "lu"，写入。

弹出 ((4,4), 1, "r")。向 l 滚回 (4,2) 得 dist = 3 > 1 不更新；向 u 被 (3,4) 的墙挡住 steps = 0；其余出界。这一支就此终结。

弹出 ((0,3), 4, "u")。向 l：先到 (0,2)，再到 (0,1) —— 正是洞，立刻 break，steps = 2，ndist = 6，路径 "ul"，写入 dist[0][1] = 6、bestPath[0][1] = "ul"。向 r 停在 (0,4)，dist = 5，写入。向 d 滚回起点，距离 8 > 0 不更新。

弹出 ((0,2), 5, "lu")。向 l：一步就踩到洞 (0,1)，steps = 1，ndist = 6。此时 dist[0][1] 也是 6，进入 tie-break："lul" 与 "ul" 比较，首字符 'l' < 'u'，所以 "lul" 更小，覆盖 bestPath[0][1] = "lul" 并重新入堆。这一步就是「同距离更新」不可省略的现场证据。

继续弹出 ((0,4), 5, "ur")，它到洞需要 3 步共 dist = 8 > 6，不更新。随后弹出 ((0,1), 6, "lul") 正常扩展（都不产生更优解），再弹出堆里残留的 ((0,1), 6, "ul") 时，因为 bestPath[0][1] 已变成 "lul"，过期校验失败被跳过——这正是第三步存在的意义。堆空，返回 "lul"，与期望一致。

代码实现

class Solution {
    private static final int INF = 1_000_000_000;
    private static final int[] DX = {1, 0, 0, -1};
    private static final int[] DY = {0, -1, 1, 0};
    private static final String[] DIR = {"d", "l", "r", "u"};

    private static class State {
        int x;
        int y;
        int dist;
        String path;

        State(int x, int y, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
    }

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length;
        int n = maze[0].length;

        int[][] dist = new int[m][n];
        String[][] bestPath = new String[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], INF);
            for (int j = 0; j < n; j++) {
                bestPath[i][j] = "";
            }
        }

        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> {
            if (a.dist != b.dist) {
                return a.dist - b.dist;
            }
            return a.path.compareTo(b.path);
        });

        dist[ball[0]][ball[1]] = 0;
        pq.offer(new State(ball[0], ball[1], 0, ""));

        while (!pq.isEmpty()) {
            State cur = pq.poll();
            if (cur.dist != dist[cur.x][cur.y] || !cur.path.equals(bestPath[cur.x][cur.y])) {
                continue;
            }

            for (int d = 0; d < 4; d++) {
                int x = cur.x;
                int y = cur.y;
                int steps = 0;

                while (true) {
                    int nx = x + DX[d];
                    int ny = y + DY[d];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    steps++;
                    if (x == hole[0] && y == hole[1]) {
                        break;
                    }
                }

                if (steps == 0) {
                    continue;
                }

                int ndist = cur.dist + steps;
                String npath = cur.path + DIR[d];

                if (ndist < dist[x][y] || (ndist == dist[x][y] && (bestPath[x][y].isEmpty() || npath.compareTo(bestPath[x][y]) < 0))) {
                    dist[x][y] = ndist;
                    bestPath[x][y] = npath;
                    pq.offer(new State(x, y, ndist, npath));
                }
            }
        }

        String answer = bestPath[hole[0]][hole[1]];
        return answer.isEmpty() ? "impossible" : answer;
    }
}

type State struct {
    x    int
    y    int
    dist int
    path string
}

type MinHeap []State

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
    if h[i].dist != h[j].dist {
        return h[i].dist < h[j].dist
    }
    return h[i].path < h[j].path
}
func (h MinHeap) Swap(i, j int)  { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)    { *h = append(*h, x.(State)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func findShortestWay(maze [][]int, ball []int, hole []int) string {
    m := len(maze)
    n := len(maze[0])

    const inf = int(1e9)
    dist := make([][]int, m)
    best := make([][]string, m)
    for i := 0; i < m; i++ {
        dist[i] = make([]int, n)
        best[i] = make([]string, n)
        for j := 0; j < n; j++ {
            dist[i][j] = inf
            best[i][j] = ""
        }
    }

    dx := []int{1, 0, 0, -1}
    dy := []int{0, -1, 1, 0}
    dir := []string{"d", "l", "r", "u"}

    dist[ball[0]][ball[1]] = 0
    best[ball[0]][ball[1]] = ""

    h := &MinHeap{}
    heap.Init(h)
    heap.Push(h, State{x: ball[0], y: ball[1], dist: 0, path: ""})

    for h.Len() > 0 {
        cur := heap.Pop(h).(State)
        if cur.dist != dist[cur.x][cur.y] || cur.path != best[cur.x][cur.y] {
            continue
        }

        for d := 0; d < 4; d++ {
            x, y := cur.x, cur.y
            steps := 0
            for {
                nx, ny := x+dx[d], y+dy[d]
                if nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1 {
                    break
                }
                x, y = nx, ny
                steps++
                if x == hole[0] && y == hole[1] {
                    break
                }
            }
            if steps == 0 {
                continue
            }

            ndist := cur.dist + steps
            npath := cur.path + dir[d]
            if ndist < dist[x][y] || (ndist == dist[x][y] && (best[x][y] == "" || npath < best[x][y])) {
                dist[x][y] = ndist
                best[x][y] = npath
                heap.Push(h, State{x: x, y: y, dist: ndist, path: npath})
            }
        }
    }

    if best[hole[0]][hole[1]] == "" {
        return "impossible"
    }
    return best[hole[0]][hole[1]]
}

复杂度分析

时间复杂度：$O(mn(m+n)\log(mn))$。凭什么：可停位置至多 $mn$ 个，每个位置最多被有效松弛常数次，每次弹出要向四个方向模拟滚动，单次滚动最长扫过一整行或一整列即 $O(m+n)$；堆操作 $O(\log(mn))$。若把路径字符串的比较也计入，还要再乘上路径长度这个因子。

空间复杂度：$O(mn \cdot L)$，其中 $L$ 为最长路径的字符数。凭什么：dist 与 bestPath 各占 $mn$ 个格子，而 bestPath 的每个格子存的是一整条移动序列；优先队列中同时存在的状态数同样是 $O(mn)$ 量级，每个状态也携带一份字符串。

关键点总结

边权是否等值决定 BFS 还是 Dijkstra。 「滚到停」把一次操作变成了不定长的位移，这是本题从迷宫 I 的 BFS 升级到迷宫 III 的 Dijkstra 的唯一原因，识别这一点比会写堆更重要。

多关键字最短路 = 把关键字打包进比较器 + 松弛条件同步扩展。 比较器写了两级，松弛条件也必须写两级（< 或 == 且更小），只改一处必然出错。

字典序作为第二关键字之所以合法，是因为前缀单调。 追加相同字符不改变两串的相对顺序，这保证了「局部最优可以拼成全局最优」，换一个不满足单调性的第二关键字（比如「转弯次数尽量多」）这套写法就不成立了。

懒删除的 Dijkstra 必须在出队时校验状态是否过期。 校验条件要覆盖全部关键字，只比 dist 会放过被字典序覆盖掉的旧路径。

steps == 0 的自环剪枝是这类「滚动 / 传送」题的固定动作。 落点等于起点的转移既无意义又会破坏终止性。

面试视角：白板上先说清三件事——「相邻停点之间边权不为 1，所以是最短路不是 BFS」「第二关键字用字典序，靠前缀单调性保证正确」「洞在中途要立即停止」。写代码时把滚动模拟单独抽成一段，讲清楚为什么判洞在前进之后。如果面试官追问优化，可以提「路径字符串可以换成记录前驱指针，最后回溯，能把空间从 $O(mn \cdot L)$ 降到 $O(mn)$」。

易错点总结

错误写法：用普通 BFS 按层数当距离 → 用例 maze 中从起点向 l 滚 1 格、向 u 滚 4 格，BFS 认为两者同层，会把 dist = 4 的 (0,3) 和 dist = 1 的 (4,2) 同等对待，最终可能输出 "ul" 而不是更优的 "lul"。

错误写法：比较器只写 a.dist - b.dist，不比路径 → 同为距离 6 的 "ul" 与 "lul" 出队顺序取决于堆的内部实现，先出的被锁定，答案退化成 "ul"。

错误写法：松弛条件只写 ndist < dist[x][y] → ((0,2), 5, "lu") 扩展出的 ("lul", 6) 因为距离不小于已有的 6 而被丢弃，输出 "ul"，字典序不是最小。

错误写法：把踩洞判断写在前进之前 → 用例中 (0,3) 向 l 滚动时，第一次循环判断当前格 (0,3) 不是洞就继续，第二次到 (0,2) 仍不是洞，第三次到 (0,1) 是洞但已经先做了移动判断，逻辑一旦写成「先判当前格再走」，球会从洞上滚过去停到 (0,0)，dist[0][1] 永远是 INF，返回 "impossible"。

错误写法：忘记 steps == 0 就跳过 → 起点 (4,3) 向 d 出界、(4,2) 向 l 撞墙，都会把自己以更长路径重新压入堆，路径无限增长，程序超时或内存溢出。

错误写法：出队时不做过期校验 → 堆里残留的 ((0,1), 6, "ul") 会被当作有效状态继续扩展，用一条已被淘汰的前缀去更新别的格子，可能把某个点的 bestPath 改成字典序更大的串。

错误写法：过期校验只写 cur.dist != dist[cur.x][cur.y] → 上一条中 "ul" 的 dist 恰好也是 6，校验通过，旧状态照样被展开，覆盖不掉的错误更隐蔽。

错误写法：方向数组按 u, d, l, r 排列并依赖遍历顺序来保证字典序 → 顺序本身不影响正确性（比较器兜底），但若同时又省掉了松弛里的字典序判断，"u" 开头的路径会先占坑，"lul" 再也写不进去。

错误写法：不可达时返回 "" 或 null → 用例中若把 hole 换成被墙围死的位置，期望输出字符串 "impossible"，返回空串直接判错。

错误写法：dist 初始化为 Integer.MAX_VALUE 后又执行 cur.dist + steps → 只要有一处误用未初始化的 dist 参与加法就会整型溢出变成负数，负距离会被误判为「更优」，答案彻底错乱；用 1e9 这类留有余量的 INF 更安全。

相似题目

题目	难度	考察点
490. 迷宫	中等	只问可达性，不关心距离，普通 DFS/BFS 即可
505. 迷宫 II	中等	要最短距离但不要路径，去掉字典序这一层即退化为单关键字 Dijkstra
743. 网络延迟时间	中等	显式给出带权边表，无需自己从网格推导边权
778. 水位上升的泳池中游泳	困难	代价是路径上的最大值而非累加和，松弛式子从 `+` 换成 `max`
787. K 站中转内最便宜的航班	中等	多一维「已用中转次数」约束，Dijkstra 需扩维或改用 Bellman-Ford
1334. 阈值距离内邻居最少的城市	中等	求全源最短路，点数小时 Floyd 比多次 Dijkstra 更好写
1631. 最小体力消耗路径	中等	网格上求「相邻高差最大值最小」，可用 Dijkstra 也可用二分 + 并查集