LeetCode 1293. 网格中的最短路径

Categories:

题目描述
思路分析
1. 解法一：BFS + 状态压缩（推荐）
相似题目

题目描述

✅ 1293. 网格中的最短路径

思路分析

解法一：BFS + 状态压缩（推荐）

核心思路：

BFS 按层扩展保证首次到达终点即最短步数。

状态包含 (r, c, rest)，其中 rest 表示剩余可消除障碍数。

用 best[r][c] 记录到达该格子时剩余的最大 rest，只有更优状态才继续扩展。

复杂度分析：

时间复杂度：O(m _ n _ k)，其中 m、n 为网格尺寸。

空间复杂度：O(m * n)，用于记录最优剩余消除次数。

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] best = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(best[i], -1);
        }

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

        int steps = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int r = cur[0];
                int c = cur[1];
                int rest = cur[2];

                if (r == m - 1 && c == n - 1) {
                    return steps;
                }

                for (int[] d : dirs) {
                    int nr = r + d[0];
                    int nc = c + d[1];

                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                        continue;
                    }

                    int nextRest = rest - grid[nr][nc];
                    if (nextRest < 0) {
                        continue;
                    }

                    // 仅当剩余消除次数更优时才入队
                    if (nextRest > best[nr][nc]) {
                        best[nr][nc] = nextRest;
                        queue.offer(new int[]{nr, nc, nextRest});
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

func shortestPath(grid [][]int, k int) int {
    m := len(grid)
    n := len(grid[0])

    best := make([][]int, m)
    for i := range best {
        best[i] = make([]int, n)
        for j := range best[i] {
            best[i][j] = -1
        }
    }

    type State struct {
        r, c, rest int
    }

    queue := make([]State, 0)
    queue = append(queue, State{0, 0, k})
    best[0][0] = k

    dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    steps := 0

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]

            if cur.r == m-1 && cur.c == n-1 {
                return steps
            }

            for _, d := range dirs {
                nr := cur.r + d[0]
                nc := cur.c + d[1]

                if nr < 0 || nr >= m || nc < 0 || nc >= n {
                    continue
                }

                nextRest := cur.rest - grid[nr][nc]
                if nextRest < 0 {
                    continue
                }

                // 仅当剩余消除次数更优时才入队
                if nextRest > best[nr][nc] {
                    best[nr][nc] = nextRest
                    queue = append(queue, State{nr, nc, nextRest})
                }
            }
        }
        steps++
    }

    return -1
}

相似题目

题目	难度	考察点
1091. 二进制矩阵中的最短路径	中等	BFS
542. 01 矩阵	中等	BFS
773. 滑动谜题	困难	BFS
127. 单词接龙	困难	BFS
864. 获取所有钥匙的最短路径	困难	BFS

本文作者: HGNULB

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