LeetCode LCP 13. 寻宝

2026-08-01 HGNULB 约 16 分钟

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

分类

题目描述

✅ LCP 13. 寻宝

题意分析

迷宫是一个字符矩阵，S 是起点、T 是终点（宝藏），M 是机关，O 是石堆，. 是可通行空地，# 是障碍。每次可以向上下左右移动一格，走一格算一步。要拿到宝藏必须先触发所有机关：触发一个机关需要在它上面放一块石头，石头只能从石堆获取，且一次只能搬运一块。求从 S 出发触发全部机关再到达 T 的最少步数，无法完成则返回 -1。

第一个关键推论来自「一次只能搬一块」：每触发一个机关就消耗一块石头，所以触发第 k 个机关之前必须先去一趟石堆。于是整条路线的形状被完全锁定了：

S → O → M(第1个) → O → M(第2个) → ... → O → M(第m个) → T

也就是说，路线是若干段「两点最短路」的拼接，我们只需要决定触发机关的顺序，以及每一段选哪个石堆中转。

第二个关键推论是：石头只影响能否触发机关，不影响通行。格子可以重复走，没有钥匙门之类的状态限制，所以任意两点间的最短距离就是一次 BFS 的结果，与手上有没有石头无关。这让上面每一段的代价都可以独立预处理，段与段之间不会互相干扰。

第三个关键推论来自数据范围：机关数量不超过 16。$2^{16}$ 这个量级是状态压缩 DP 的标志性信号。既然要在 16 个机关上求一个最优访问顺序，这就是一个带起点终点的旅行商问题（TSP），用「已触发机关集合 + 当前所在机关」作为状态即可。

边界情况：机关数为 0 时不需要石头，答案就是 S 到 T 的 BFS 距离；有机关但没有石堆、或某个机关/石堆被障碍完全封死时，返回 -1。

解法：多源 BFS 预处理 + 状态压缩 DP

核心思路

把问题拆成「算距离」和「定顺序」两层。

第一层：BFS 预处理所有需要的距离。 因为通行不带状态，每次 BFS 就能求出一个源点到全图所有格子的最短距离。需要的源点有：起点 S、终点 T、以及每一个机关 M。共 m + 2 次 BFS，每次 $O(rc)$。

注意这里有个省事的技巧：不需要从石堆出发做 BFS。因为距离是对称的（无向图上双向可走、边权都是 1），「机关 i 到石堆 o 的距离」直接从「以机关 i 为源点的 BFS 结果」里读 o 这个格子即可。这把 BFS 次数从 m + |O| + 2 降到了 m + 2。

第二层：把段代价整理成 TSP 的边权。

startCost[i]：从 S 出发、取一块石头、触发机关 i 的最短步数，等于 min over o (distS[o] + distM[i][o])——枚举中转的石堆取最小。

cost[i][j]：站在机关 i 上，去取一块石头再触发机关 j 的最短步数，等于 min over o (distM[i][o] + distM[j][o])。

endCost[i]：触发完机关 i 后直接走到 T 的步数，等于以 T 为源点的 BFS 结果在机关 i 处的值（同样利用对称性）。

第三层：状态压缩 DP 求最优顺序。 定义 dp[mask][i] 为「已触发的机关集合恰好是 mask，且当前正站在机关 i 上」时的最少步数（要求 i ∈ mask）。

初始：dp[1<<i][i] = startCost[i]，表示第一个触发的是机关 i。

转移：dp[mask | 1<<j][j] = min(dp[mask][i] + cost[i][j])，其中 i ∈ mask、j ∉ mask。

答案：min over i (dp[full][i] + endCost[i])，full 是全 1 掩码。

转移的正确性依赖前面那条「段与段独立」的推论：从机关 i 到机关 j 的代价只取决于 i 和 j，与之前触发过哪些机关无关，因此才能把历史压缩成一个集合而丢弃具体路径。

按 mask 递增的顺序枚举可以保证无后效性——转移只会从 mask 走向 mask | 1<<j，而后者的数值严格更大，所以被更新时它自己还没有被当作转移源使用过。

解题步骤

扫描矩阵：一次遍历记下 S、T 的坐标，收集所有 M 与 O 的坐标列表。机关的下标顺序就是后面位掩码里的位序。

BFS 起点：先求 distStart。若机关数为 0，直接返回 distStart[T]（不可达则 -1），这条捷径必须放在最前面，否则后面对空机关集合做 DP 会得到 full - 1 = 0 这样的退化状态。

BFS 终点与每个机关：求 distTarget 和 distMachine[i]。BFS 用普通队列即可，因为边权全为 1；# 视为不可进入，已访问的格子用「距离仍是 INF」来判定，不需要额外的 visited 数组。

算 startCost 与 endCost：对每个机关枚举所有石堆取最小；同时读出终点 BFS 在该机关处的值。任何一个机关的 startCost 或 endCost 不可达，就可以立刻返回 -1——这个机关永远无法被触发，或触发后回不到终点。石堆列表为空时 startCost 自然保持 INF，这条判断顺带覆盖了「有机关但没石堆」的情形。

算 cost[i][j]：双重循环机关、内层枚举石堆。cost[i][i] 会被算出来但永远不会被用到（转移要求 j ∉ mask），不必特殊处理。

DP 初始化：dp 全部置为 INF，再对每个 i 令 dp[1<<i][i] = startCost[i]。

DP 转移：mask 从 1 递增到 2^m - 1，跳过 i ∉ mask 或 dp[mask][i] 仍为 INF 的状态（后者是剪枝，也避免 INF 参与加法），再枚举 j ∉ mask 松弛。

收尾：在满集合状态上加 endCost[i] 取最小；若仍是 INF 返回 -1。

以官方样例 maze = ["S#O", "M..", "M.T"] 走一遍。坐标：S=(0,0)、石堆 O=(0,2)、M0=(1,0)、M1=(2,0)、T=(2,2)，障碍在 (0,1)。

BFS 结果的关键值：distStart[O] = 4（S 被障碍挡住，只能绕行 (1,0)→(1,1)→(1,2)→(0,2)）；distM0[O] = 3；distM1[O] = 4；distTarget[M0] = 3；distTarget[M1] = 2。

于是 startCost[0] = 4 + 3 = 7，startCost[1] = 4 + 4 = 8，cost[0][1] = cost[1][0] = 3 + 4 = 7。

DP：dp[{0}][0] = 7、dp[{1}][1] = 8；dp[{0,1}][1] = 7 + 7 = 14、dp[{0,1}][0] = 8 + 7 = 15。

收尾比较两条路线：先 M0 再 M1，14 + endCost[1] = 14 + 2 = 16；先 M1 再 M0，15 + endCost[0] = 15 + 3 = 18。答案 16，与期望输出一致。这里也能看出为什么必须枚举「最后停在哪个机关」——两条顺序的 DP 值只差 1，但收尾距离差了 1，光看 DP 值会选错。

再看 maze = ["S#O", "M.#", "M.T"]：石堆 (0,2) 的两个邻居 (0,1) 和 (1,2) 都是障碍，它被彻底封死，distStart[O] 为 INF，于是 startCost[0] 保持 INF，直接返回 -1。

代码实现

class Solution {
    private static final int INF = 1 << 29;
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minimalSteps(String[] maze) {
        int rows = maze.length;
        int cols = maze[0].length();
        int[] start = null;
        int[] target = null;
        List<int[]> machines = new ArrayList<>();
        List<int[]> stones = new ArrayList<>();

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                char ch = maze[r].charAt(c);
                if (ch == 'S') {
                    start = new int[] {r, c};
                } else if (ch == 'T') {
                    target = new int[] {r, c};
                } else if (ch == 'M') {
                    machines.add(new int[] {r, c});
                } else if (ch == 'O') {
                    stones.add(new int[] {r, c});
                }
            }
        }

        int m = machines.size();
        int[][] distStart = bfs(maze, start[0], start[1]);
        // 没有机关时不需要石头，直接走到终点。
        if (m == 0) {
            int direct = distStart[target[0]][target[1]];
            return direct >= INF ? -1 : direct;
        }

        int[][] distTarget = bfs(maze, target[0], target[1]);
        int[][][] distMachine = new int[m][][];
        for (int i = 0; i < m; i++) {
            distMachine[i] = bfs(maze, machines.get(i)[0], machines.get(i)[1]);
        }

        int[] startCost = new int[m];
        int[] endCost = new int[m];
        for (int i = 0; i < m; i++) {
            startCost[i] = INF;
            for (int[] stone : stones) {
                int toStone = distStart[stone[0]][stone[1]];
                int backToMachine = distMachine[i][stone[0]][stone[1]];
                if (toStone < INF && backToMachine < INF) {
                    startCost[i] = Math.min(startCost[i], toStone + backToMachine);
                }
            }
            // 距离对称，终点 BFS 的结果直接给出机关到终点的步数。
            endCost[i] = distTarget[machines.get(i)[0]][machines.get(i)[1]];
            if (startCost[i] >= INF || endCost[i] >= INF) {
                return -1;
            }
        }

        int[][] cost = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                cost[i][j] = INF;
                for (int[] stone : stones) {
                    int fromI = distMachine[i][stone[0]][stone[1]];
                    int toJ = distMachine[j][stone[0]][stone[1]];
                    if (fromI < INF && toJ < INF) {
                        cost[i][j] = Math.min(cost[i][j], fromI + toJ);
                    }
                }
            }
        }

        int full = 1 << m;
        int[][] dp = new int[full][m];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        for (int i = 0; i < m; i++) {
            dp[1 << i][i] = startCost[i];
        }

        for (int mask = 1; mask < full; mask++) {
            for (int i = 0; i < m; i++) {
                if ((mask & (1 << i)) == 0 || dp[mask][i] >= INF) {
                    continue;
                }
                for (int j = 0; j < m; j++) {
                    if ((mask & (1 << j)) != 0 || cost[i][j] >= INF) {
                        continue;
                    }
                    int next = mask | (1 << j);
                    dp[next][j] = Math.min(dp[next][j], dp[mask][i] + cost[i][j]);
                }
            }
        }

        int ans = INF;
        for (int i = 0; i < m; i++) {
            if (dp[full - 1][i] < INF) {
                ans = Math.min(ans, dp[full - 1][i] + endCost[i]);
            }
        }

        return ans >= INF ? -1 : ans;
    }

    private int[][] bfs(String[] maze, int sr, int sc) {
        int rows = maze.length;
        int cols = maze[0].length();
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) {
            Arrays.fill(row, INF);
        }
        dist[sr][sc] = 0;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {sr, sc});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : DIRS) {
                int nr = cur[0] + dir[0];
                int nc = cur[1] + dir[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                    continue;
                }
                // 距离仍是 INF 等价于尚未访问，省掉额外的 visited 数组。
                if (maze[nr].charAt(nc) == '#' || dist[nr][nc] < INF) {
                    continue;
                }
                dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                queue.offer(new int[] {nr, nc});
            }
        }

        return dist;
    }
}

const inf = 1 << 29

func minimalSteps(maze []string) int {
    rows, cols := len(maze), len(maze[0])
    var start, target [2]int
    machines := make([][2]int, 0, 16)
    stones := make([][2]int, 0)

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            switch maze[r][c] {
            case 'S':
                start = [2]int{r, c}
            case 'T':
                target = [2]int{r, c}
            case 'M':
                machines = append(machines, [2]int{r, c})
            case 'O':
                stones = append(stones, [2]int{r, c})
            }
        }
    }

    m := len(machines)
    distStart := bfsMaze(maze, start[0], start[1])
    // 没有机关时不需要石头，直接走到终点。
    if m == 0 {
        if distStart[target[0]][target[1]] >= inf {
            return -1
        }
        return distStart[target[0]][target[1]]
    }

    distTarget := bfsMaze(maze, target[0], target[1])
    distMachine := make([][][]int, m)
    for i, machine := range machines {
        distMachine[i] = bfsMaze(maze, machine[0], machine[1])
    }

    startCost := make([]int, m)
    endCost := make([]int, m)
    for i := 0; i < m; i++ {
        startCost[i] = inf
        for _, stone := range stones {
            toStone := distStart[stone[0]][stone[1]]
            backToMachine := distMachine[i][stone[0]][stone[1]]
            if toStone < inf && backToMachine < inf && toStone+backToMachine < startCost[i] {
                startCost[i] = toStone + backToMachine
            }
        }
        // 距离对称，终点 BFS 的结果直接给出机关到终点的步数。
        endCost[i] = distTarget[machines[i][0]][machines[i][1]]
        if startCost[i] >= inf || endCost[i] >= inf {
            return -1
        }
    }

    cost := make([][]int, m)
    for i := 0; i < m; i++ {
        cost[i] = make([]int, m)
        for j := 0; j < m; j++ {
            cost[i][j] = inf
            for _, stone := range stones {
                fromI := distMachine[i][stone[0]][stone[1]]
                toJ := distMachine[j][stone[0]][stone[1]]
                if fromI < inf && toJ < inf && fromI+toJ < cost[i][j] {
                    cost[i][j] = fromI + toJ
                }
            }
        }
    }

    full := 1 << m
    dp := make([][]int, full)
    for mask := range dp {
        dp[mask] = make([]int, m)
        for i := range dp[mask] {
            dp[mask][i] = inf
        }
    }
    for i := 0; i < m; i++ {
        dp[1<<i][i] = startCost[i]
    }

    for mask := 1; mask < full; mask++ {
        for i := 0; i < m; i++ {
            if mask&(1<<i) == 0 || dp[mask][i] >= inf {
                continue
            }
            for j := 0; j < m; j++ {
                if mask&(1<<j) != 0 || cost[i][j] >= inf {
                    continue
                }
                next := mask | 1<<j
                if dp[mask][i]+cost[i][j] < dp[next][j] {
                    dp[next][j] = dp[mask][i] + cost[i][j]
                }
            }
        }
    }

    ans := inf
    for i := 0; i < m; i++ {
        if dp[full-1][i] < inf && dp[full-1][i]+endCost[i] < ans {
            ans = dp[full-1][i] + endCost[i]
        }
    }
    if ans >= inf {
        return -1
    }
    return ans
}

func bfsMaze(maze []string, sr int, sc int) [][]int {
    rows, cols := len(maze), len(maze[0])
    dist := make([][]int, rows)
    for r := range dist {
        dist[r] = make([]int, cols)
        for c := range dist[r] {
            dist[r][c] = inf
        }
    }
    dist[sr][sc] = 0

    dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    queue := [][2]int{{sr, sc}}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        for _, dir := range dirs {
            nr, nc := cur[0]+dir[0], cur[1]+dir[1]
            if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
                continue
            }
            // 距离仍是 inf 等价于尚未访问，省掉额外的 visited 数组。
            if maze[nr][nc] == '#' || dist[nr][nc] < inf {
                continue
            }
            dist[nr][nc] = dist[cur[0]][cur[1]] + 1
            queue = append(queue, [2]int{nr, nc})
        }
    }

    return dist
}

复杂度分析

记矩阵为 r × c，机关数为 m（不超过 16），石堆数为 k。

时间复杂度：$O((m + 2) \cdot rc + m^2 k + 2^m \cdot m^2)$。三项分别是 BFS 预处理、整理 TSP 边权、状态压缩 DP。DP 那一项是渐进上的主导：m = 16 时 $2^{16} \times 16^2 \approx 1.7 \times 10^7$，完全可以接受。

空间复杂度：$O(m \cdot rc + 2^m \cdot m)$。前者是 m + 2 张距离矩阵，后者是 DP 表；m = 16 时 DP 表约 $10^6$ 个整数。

关键点总结

「一次只能搬一块石头」直接锁定了路线形状 S → O → M → O → M → ... → T，把一道看起来很自由的迷宫题压成了「决定机关访问顺序」这一个决策。

石头不影响通行，所以两点间距离与携带状态无关，各段代价可以独立预处理——这是能把路径问题降维成图上 TSP 的前提。如果题目改成「带石头时不能通过某些格子」，这套分解立刻失效。

边权全为 1 时 BFS 就是最短路，且距离对称，所以从机关出发的 BFS 结果可以反过来读出「机关到石堆」的距离，不必再从石堆做 BFS。

2^{16} 量级的组合数是状态压缩 DP 的标志。状态设计成「已完成集合 + 当前位置」而非只有集合，是因为下一段的代价依赖当前站在哪里。

按 mask 递增枚举天然满足无后效性，因为转移只会让 mask 的数值变大。

起点段和终点段要单独处理：startCost 需要经石堆中转，endCost 是直达，两者形状不同，不能混进 cost 矩阵。

易错点总结

漏掉机关数为 0 的分支：此时 full - 1 = 0，DP 循环不会执行，答案会错成 -1 或越界。必须在 DP 之前直接返回 S 到 T 的 BFS 距离。

忘记「终点段」也可能不可达：只检查 startCost 不够，机关触发后走不到 T 同样是 -1。

让 INF 参与加法：不加 < INF 判断就把两个不可达距离相加，会得到一个巨大但仍小于初始 ans 的假值。INF 取 1 << 29 而不是 Integer.MAX_VALUE，就是为了留出加法余量。

忽略「有机关但没有石堆」：石堆列表为空时 startCost 会保持 INF，只要保留那条判断就自动返回 -1；若直接跳过判断则会得到错误结果。

把 endCost 也算成要经石堆中转：最后一个机关触发完就可以直奔终点，中间不需要再取石头。

状态只用集合不带当前位置：dp[mask] 无法确定下一段从哪里出发，转移代价失去依据，这是本题最典型的状态设计错误。

DP 收尾只取 dp[full-1] 的最小值：必须加上各自的 endCost[i] 再比较。样例一里 DP 值更小的那条路线，加上收尾距离后反而更差。

BFS 用 DFS 代替：边权虽然全是 1，但 DFS 求出的不是最短距离。

忘记障碍判断或越界判断：# 必须视为不可进入；同时矩阵可能是长条形（行列数不等），越界检查要分别用 rows 和 cols。

相似题目

题目	难度	考察点
847. 访问所有节点的最短路径	困难	同样是「集合 + 当前位置」的状态压缩，但直接在图上做 BFS
980. 不同路径 III	困难	网格上要求走遍所有空地，可用状态压缩替代回溯的访问标记
542. 01 矩阵	中等	网格 BFS 求最短距离的基础题，本题预处理层的裸版本
1031. 两个无重叠子数组的最大和	中等	同属「把整体最优拆成若干独立段再拼接」的思路，维度低得多