LeetCode LCP 13. 寻宝
题目描述
题意分析
在迷宫中从
S出发，把石头放到每个M上保持机关触发，最后到T取宝藏，求最少移动步数。每个O有无限石头，一次只能搬一块，拿起和放下不计步数。只有#不能通过，石堆、机关和终点无论当前是否触发都可以经过。
解法：多次单源 BFS + 状态压缩动态规划
核心思路
[!blue]
直接在迷宫里同时记录位置、持石状态和机关集合会产生大量状态。可以改为只记录“刚刚放下一块石头、触发一个机关”的时刻：此时位置在该机关，手上没有石头，下一次触发机关之前必然要重新经过某个石堆取石。机关最多 16 个，适合把这些触发阶段单独做状态压缩。
首先忽略取放石头的动作，只计算普通步行距离。网格每一步代价都为一，从起点、终点以及每个机关分别做 BFS，得到它们到各格的最短距离。第一次发现某格就记下距离，之后不再入队；距离保持
INF表示不可达。机关触发与否不改变通路，因此这些距离不会随机关集合变化。设
dist(a, b)为步行距离。触发第一个机关i的代价是startCost[i] = min(dist(S, O) + dist(O, Mi))；触发机关i后再触发j的代价是cost[i][j] = min(dist(Mi, O) + dist(O, Mj))。两个最小值都枚举所有可达石堆O。道路无向，所以从机关出发的 BFS 距离也能反过来作为石堆到机关的距离，不需要从每个石堆再做 BFS。全部机关完成后已经不必取新石头，最后一段直接使用
endCost[i] = dist(Mi, T)。这些阶段可以独立组合：石堆无限供应，取放不计步数，经过其他机关或终点也不必立刻触发或结束。固定一个机关顺序后，每段分别取最短路线，就能得到该顺序下的最小总代价。定义
dp[mask][i]为已经触发mask中的机关、最后刚在机关i放下石头时的最少步数。mask的第i位为一表示该机关已经完成。只有集合还不够，因为停在哪个机关决定下一段距离；持石状态则无需另存，因为所有 DP 状态都统一为空手。初始化
dp[1 << i][i] = startCost[i]，表示第一个触发机关可以任选。对于任一可达状态，枚举尚未触发的j，用dp[mask][i] + cost[i][j]更新dp[mask | (1 << j)][j]。每次只新增一个机关，集合严格扩大，设置一个原本为零的位也会让数值变大，所以按mask递增遍历时，前置状态已经计算完。所有触发顺序都能从单机关状态逐个扩展出来，每个阶段又使用该顺序下的最小代价，因此满集合状态覆盖了全局最优方案。最后枚举最后一个机关，取
dp[full - 1][i] + endCost[i]的最小值。无机关时直接返回
S到T的距离，不需要找石头。有机关时，如果某个startCost[i]或endCost[i]不可达，就能直接判无解：任何完整路线都必须让起点、该机关、至少一个可取用石堆和终点处于同一片连通区域，后续触发不会打开新道路。单个无关石堆不可达则不影响结论，求最小值时跳过它即可。
解题步骤
- 扫描起点、终点、机关和石堆位置，从起点做 BFS；没有机关时直接处理终点距离。
- 从终点和每个机关继续做 BFS，保存步行距离。
- 枚举石堆，预处理
startCost和cost；同时取得endCost，排除必然无解的机关。- 将 DP 初始化为
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
}
复杂度分析
- 时间复杂度：$O((m+2)rc+m^2k+2^m m^2)$，其中
m为机关数、k为石堆数，网格为r × c。最多执行m+2次 BFS；枚举机关对和石堆得到阶段代价；DP 有 $2^m m$ 个状态，每个最多枚举m个下一机关。- 空间复杂度：$O((m+2)rc+2^m m+m^2)$，分别用于 BFS 距离表、DP 状态表和机关间阶段代价，BFS 队列与位置列表也被该上界包含。
关键点总结
[!green]
- 把状态统一放在触发机关后的空手时刻，持石过程并入阶段代价。
- 每个机关间的转移都要经过石堆，完成全部机关后的最后一段才直接走向终点。
- 通行条件不随触发状态改变，预处理的最短阶段可以独立拼接。
- 状态必须同时包含已完成集合和最后所在机关。
易错点总结
[!yellow]
- 直接使用两个机关间的步行距离，会漏掉搬下一块石头的路程。
- 把未触发机关或未满足条件的终点当墙，会排除题目允许经过的路线。
- 只保存机关集合而不保存最后位置，无法确定后续阶段的成本。
- 满集合后立即返回，会漏算最后机关到宝藏的路程。
- 不可达状态必须用
INF区分并跳过，不能让默认零值参与最小费用更新。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 847. 访问所有节点的最短路径 | 困难 | 先把石堆中转代价计入机关之间的距离，再以已触发集合和当前位置做状态，类似全节点访问问题。 |
| 864. 获取所有钥匙的最短路径 | 困难 | 钥匙获得后可持续使用，本题石头每次触发机关后被消耗，需重新取石，资源语义不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！