1293. 网格中的最短路径

题目描述

输入一个 m x n 的网格 grid 和整数 k。0 表示空地，1 表示障碍。

每一步可以向上、下、左、右移动一格，只能走到空地上。你最多可以清除 k 个障碍，被清除的格子就可以通行。

返回从左上角 (0, 0) 走到右下角 (m - 1, n - 1) 的最少步数。如果无论怎样都到不了，返回 -1。

示例 1

输入：grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
k = 1
输出：6

解释：不清除障碍最少要 10 步；清除 (3,2) 后可以沿右侧直下，共 6 步。

示例 2

输入：grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
输出：-1

解释：至少要清除两个障碍才能走通，而 k = 1。

数据范围

grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] 是 0 或 1。
grid[0][0] == grid[m-1][n-1] == 0

解题思路

状态是 (行, 列, 剩余可消除次数)。按层 BFS，每层代表走了相同的步数。进入障碍格要消耗 1 次。剪枝：best[x][y] 记录迄今到达 (x,y) 时最多的剩余次数，只有剩余次数更多时才值得再入队——步数不更少、剩余也不更多的状态不可能更优。

为什么正确

第 s 层的状态都是恰好走 s 步能到达、且不被更早状态支配的状态。

复杂度分析

状态数 O(mnk)，时间和空间都是 O(mnk)。

易错点

只用 visited[x][y] 一维去重是错的：先到达但消除次数已用光的状态，不能代替稍晚到达但还有余力的状态。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        best = [[-1] * n for _ in range(m)]
        best[0][0] = k
        queue = [(0, 0, k)]
        steps = 0
        while queue:
            if any(i == m - 1 and j == n - 1 for i, j, _ in queue):
                return steps
            nxt = []
            for i, j, r in queue:
                for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= x < m and 0 <= y < n:
                        left = r - grid[x][y]
                        if left > best[x][y]:
                            best[x][y] = left
                            nxt.append((x, y, left))
            queue = nxt
            steps += 1
        return -1

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] best = new int[m][n];
        for (int[] row : best) Arrays.fill(row, -1);
        best[0][0] = k;
        List<int[]> queue = new ArrayList<>();
        queue.add(new int[]{0, 0, k});
        int steps = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            for (int[] s : queue)
                if (s[0] == m - 1 && s[1] == n - 1) return steps;
            List<int[]> nxt = new ArrayList<>();
            for (int[] s : queue) {
                for (int[] d : dirs) {
                    int x = s[0] + d[0], y = s[1] + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        int left = s[2] - grid[x][y];
                        if (left > best[x][y]) {
                            best[x][y] = left;
                            nxt.add(new int[]{x, y, left});
                        }
                    }
                }
            }
            queue = nxt;
            steps++;
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> best(m, vector<int>(n, -1));
        best[0][0] = k;
        vector<array<int, 3>> queue = {{0, 0, k}};
        int steps = 0;
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.empty()) {
            for (auto& s : queue)
                if (s[0] == m - 1 && s[1] == n - 1) return steps;
            vector<array<int, 3>> nxt;
            for (auto& s : queue) {
                for (auto& d : dirs) {
                    int x = s[0] + d[0], y = s[1] + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        int left = s[2] - grid[x][y];
                        if (left > best[x][y]) {
                            best[x][y] = left;
                            nxt.push_back({x, y, left});
                        }
                    }
                }
            }
            queue = nxt;
            steps++;
        }
        return -1;
    }
};

func shortestPath(grid [][]int, k int) int {
	m, n := len(grid), 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
		}
	}
	best[0][0] = k
	queue := [][3]int{{0, 0, k}}
	steps := 0
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	for len(queue) > 0 {
		for _, s := range queue {
			if s[0] == m-1 && s[1] == n-1 {
				return steps
			}
		}
		nxt := [][3]int{}
		for _, s := range queue {
			for _, d := range dirs {
				x, y := s[0]+d[0], s[1]+d[1]
				if x >= 0 && x < m && y >= 0 && y < n {
					left := s[2] - grid[x][y]
					if left > best[x][y] {
						best[x][y] = left
						nxt = append(nxt, [3]int{x, y, left})
					}
				}
			}
		}
		queue = nxt
		steps++
	}
	return -1
}

var shortestPath = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const best = Array.from({ length: m }, () => new Array(n).fill(-1));
    best[0][0] = k;
    let queue = [[0, 0, k]];
    let steps = 0;
    while (queue.length) {
        if (queue.some(([i, j]) => i === m - 1 && j === n - 1)) {
            return steps;
        }
        const nxt = [];
        for (const [i, j, r] of queue) {
            for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    const left = r - grid[x][y];
                    if (left > best[x][y]) {
                        best[x][y] = left;
                        nxt.push([x, y, left]);
                    }
                }
            }
        }
        queue = nxt;
        steps++;
    }
    return -1;
};

function shortestPath(grid: number[][], k: number): number {
    const m = grid.length, n = grid[0].length;
    const best = Array.from({ length: m }, () => new Array(n).fill(-1));
    best[0][0] = k;
    let queue: number[][] = [[0, 0, k]];
    let steps = 0;
    while (queue.length) {
        if (queue.some(([i, j]) => i === m - 1 && j === n - 1)) {
            return steps;
        }
        const nxt: number[][] = [];
        for (const [i, j, r] of queue) {
            for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    const left = r - grid[x][y];
                    if (left > best[x][y]) {
                        best[x][y] = left;
                        nxt.push([x, y, left]);
                    }
                }
            }
        }
        queue = nxt;
        steps++;
    }
    return -1;
}

载入编辑器，自己跑一遍 →

图论专题的其他题目

查看图论全部题目 →