LeetCode 1293. 网格中的最短路径

2025-01-16 HGNULB 约 8 分钟

文章信息 10 个分类 3 个标签

分类

LeetCode CodeTop 困难未解决 5-10 字节亚马逊京东百度快手

题目描述

✅ 1293. 网格中的最短路径

题意分析

从网格左上角走到右下角，每次只能向上、下、左、右移动一格。空格可以直接通过，障碍格需要消耗一次消除机会，总共最多使用 k 次，求最少移动步数，无法到达时返回 -1。

起点和终点都是空地，步数按移动的边数计算。同一个位置可能通过不同路线到达，已经走过的步数和剩余消除机会都会影响后续选择，不能只把格子分成访问过或未访问过。

解法：BFS + 剩余消除次数剪枝

核心思路

[!blue]

每次移动代价都为 1，适合按步数分层 BFS。完整状态除了行、列，还要携带剩余消除次数 remain：走入空地保持次数，走入障碍减一，次数为负时这条路线不可行。

为同一格保存所有剩余次数虽可行，但有些状态没有继续搜索的价值。若另一条路线用了不更多的步数到达同一位置，而且剩余额度不少，那么它能接上当前路线的任何后续路径，总步数也不会更多，当前状态就被这条路线覆盖。

用 best[row][col] 记录已经入队过的最大剩余额度。BFS 按层产生候选，当检查一个新候选时，此前入队的状态距离都不大于它；因此只需再比较额度。nextRemain <= best 时可以拒绝，只有严格提高该格历史额度的候选才入队。后来以更多步数、更多额度到达仍然可能有用，所以不能永久封闭这个格子。

best 初值为 -1，表示尚未到达，额度为 0 的状态仍应允许入队。每层开始固定队列大小，新加入的状态属于下一层；终点第一次出队时，所在层数就是最少步数。队列耗尽还没到终点，才说明不存在可行路径。

搜索前还能使用距离下界：无障碍时最短需要 rows + cols - 2 步，任何路线都不能更短。一条只向右、向下的路径有这么多步，起终点为空，中间至多有“距离减一”个障碍；若 k 足够清除这些位置，就一定能达到这个下界，可以直接返回。单格网格则无需移动。

解题步骤

计算曼哈顿距离；距离为 0 返回 0，额度至少为“距离减一”时返回该距离。

将二维 best 全部初始化为 -1，起点以完整额度入队，并登记其额度。

按层处理队列，每层固定已有状态数量；弹出终点时返回当前步数。

检查四个方向，对未越界邻居计算 nextRemain = remain - grid[nextRow][nextCol]。

额度非负且严格大于该位置历史最大值时，先更新 best，再把新状态加入队列。

一层处理完步数加一；搜索耗尽仍未找到终点，返回 -1。

代码实现

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

    public int shortestPath(int[][] grid, int k) {
        int rows = grid.length;
        int cols = grid[0].length;
        int distance = rows + cols - 2;

        if (distance == 0) {
            return 0;
        }

        // 起终点为空，最短曼哈顿路径中间最多消耗距离减一份额度
        if (k >= distance - 1) {
            return distance;
        }

        int[][] best = new int[rows][cols];

        for (int[] row : best) {
            // 负一表示尚未到达，零额度也是有效状态
            Arrays.fill(row, -1);
        }

        Queue<int[]> queue = new ArrayDeque<>();

        queue.offer(new int[] {
            0,
            0,
            k
        });
        best[0][0] = k;

        for (int steps = 0; !queue.isEmpty(); steps++) {
            // 固定本层数量，新加入状态属于下一步数层
            for (int size = queue.size(); size > 0; size--) {
                int[] state = queue.poll();
                int row = state[0];
                int col = state[1];
                int remain = state[2];

                if (row == rows - 1 && col == cols - 1) {
                    return steps;
                }

                for (int d = 0; d < 4; d++) {
                    int nextRow = row + DIRS[d];
                    int nextCol = col + DIRS[d + 1];

                    if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
                        continue;
                    }

                    int nextRemain = remain - grid[nextRow][nextCol];

                    if (nextRemain < 0 || nextRemain <= best[nextRow][nextCol]) {
                        continue;
                    }

                    // 入队前登记更多剩余额度，距离顺序由分层搜索保证
                    best[nextRow][nextCol] = nextRemain;
                    queue.offer(new int[] {
                        nextRow,
                        nextCol,
                        nextRemain
                    });
                }
            }
        }

        return -1;
    }
}

func shortestPath(grid [][]int, k int) int {
    rows, cols := len(grid), len(grid[0])
    distance := rows + cols - 2
    if distance == 0 {
        return 0
    }
    // 起终点为空，最短曼哈顿路径中间最多消耗距离减一份额度
    if k >= distance-1 {
        return distance
    }

    best := make([][]int, rows)
    for row := range best {
        best[row] = make([]int, cols)
        for col := range best[row] {
            // 负一表示尚未到达，零额度也是有效状态
            best[row][col] = -1
        }
    }

    type state struct {
        row, col, remain int
    }
    dirs := [5]int{
        1,
        0,
        -1,
        0,
        1,
    }
    queue := []state{
        {row: 0, col: 0, remain: k},
    }
    best[0][0] = k

    for steps := 0; len(queue) > 0; steps++ {
        // 固定本层数量，新加入状态属于下一步数层
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[i]
            if cur.row == rows-1 && cur.col == cols-1 {
                return steps
            }

            for d := 0; d < 4; d++ {
                nextRow := cur.row + dirs[d]
                nextCol := cur.col + dirs[d+1]
                if nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols {
                    continue
                }

                nextRemain := cur.remain - grid[nextRow][nextCol]
                if nextRemain < 0 ||
                    nextRemain <= best[nextRow][nextCol] {
                    continue
                }

                // 入队前登记更多剩余额度，距离顺序由分层搜索保证
                best[nextRow][nextCol] = nextRemain
                queue = append(queue, state{
                    row: nextRow, col: nextCol, remain: nextRemain,
                })
            }
        }
        queue = queue[size:]
    }
    return -1
}

复杂度分析

设网格有 m 行、n 列。直接达到距离下界时只需常数时间和空间；以下分析实际进入 BFS 的情况。

时间复杂度：$O(mn(k+1))$ 上界。每个格子的已登记额度只能严格增加，最多接受 k + 1 种非负额度，每个状态只检查四个方向。

空间复杂度：$O(mn(k+1))$ 队列上界，二维 best 另占 $O(mn)$。提前返回条件使实际搜索时的 k 小于 m + n，但队列仍可能包含同一格的多个资源状态。

关键点总结

[!green]

剩余额度属于搜索状态，位置相同不代表后续能力相同。

支配判断同时需要步数不更多、资源不少，BFS 的入队顺序提供了前一个条件。

二维表只是压缩重复判断，不代表队列也只会保存每格一个状态。

曼哈顿距离是下界，额度足够时还能构造达到下界的路径，因此可以提前返回。

易错点总结

[!yellow]

只按位置设置布尔访问标记，会拒绝后来携带更多消除机会的有效路线。

将 best 默认初始化为 0，会把第一次恰好用完额度到达的状态也拒绝。

没有扣除目标格的障碍消耗，就可能让没有额度的状态穿过障碍。

本剪枝用于新候选入队，不能脱离 BFS 的距离顺序只比较两个任意状态的额度。

将新加入的状态继续算进同一层，会破坏最短步数的对应关系。

声称额外空间只有二维表大小，会忽略队列中同一格的多种额度状态。

相似题目

题目	难度	关联与区别
1091. 二进制矩阵中的最短路径	中等	本题允许消除障碍且只走四方向，原题只走空格并允许八方向，状态与邻居规则不同。
1129. 颜色交替的最短路径	中等	同样需要位置之外的状态来判断重复访问，本题记剩余消障次数，原题记上一条边颜色。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/51513208

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！