1293：网格中的最短路径（1967 分）

2019-12-15 约 560 字预计阅读 2 分钟次阅读

力扣第 167 场周赛第 4 题

题目

给你一个 m * n 的网格，其中每个单元格不是 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 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2：

输入：grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
输出：-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

相似问题：

分析

#1

将（当前位置，经过障碍数）看作状态，即是典型的 bfs 问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m,n = len(grid),len(grid[0])
        Q = deque([(0,0,0,k)])
        vis = {(0,0,k)}
        while Q:
            w,i,j,k = Q.popleft()
            if (i,j)==(m-1,n-1):
                return w
            for x,y in [(i-1,j),(i,j-1),(i+1,j),(i,j+1)]:
                if 0<=x<m and 0<=y<n:
                    k2 = k-grid[x][y]
                    if k2>=0 and (x,y,k2) not in vis:
                        vis.add((x,y,k2))
                        Q.append((w+1,x,y,k2))
        return -1

467 ms

#2

针对 k 有个剪枝：

若没有障碍，最短即是 m+n-2，除起始点外经过 m+n-3 个格子
因此若 k>=m+n-3，直接返回即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m,n = len(grid),len(grid[0])
        if k>=m+n-3:
            return m+n-2
        Q = deque([(0,0,0,k)])
        vis = {(0,0,k)}
        while Q:
            w,i,j,k = Q.popleft()
            if (i,j)==(m-1,n-1):
                return w
            for x,y in [(i-1,j),(i,j-1),(i+1,j),(i,j+1)]:
                if 0<=x<m and 0<=y<n:
                    k2 = k-grid[x][y]
                    if k2>=0 and (x,y,k2) not in vis:
                        vis.add((x,y,k2))
                        Q.append((w+1,x,y,k2))
        return -1

7 ms

目录

1293：网格中的最短路径（1967 分）

题目

分析

#1

#2

解答