Leetcode 1293：网格中的最短路径（超详细的解法！！！）_1293. 网格中的最短路径

给你一个 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). 
1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

输入：
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。 
1
2
3
4
5
6
7
8
9

提示：

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] == 0 or 1
• grid[0][0] == grid[m-1][n-1] == 0

解题思路

最短路经问题直接使用bfs，需要注意的是遍历的过程中记录的访问节点。传统的bfs记录横纵坐标即可，但是这个问题多个了参数k，所以我们还需记录k的数值。这里有两种方案，一种是采用set记录(x,y,k)，另一种是通过dict记录key:(x,y)和value:k（我这里使用第二种）。

如果采用第一种方案的话，就是最原始的写法，只要判断(x,y,k)是不是之前访问过即可；但如果采用第二种写法的话，我们就需要判断原来(x,y)的值k1（初始状态为inf）比当前遍历到的(x,y)的值k2小，那么需要将原来的k1更新为k2。

如果k>=r+c-3的话，那么就算是所有网络都是1，我们也可以在r+c-2的步数内实现。

class Solution:
    def shortestPath(self, g: List[List[int]], k: int) -> int:
        r, c = len(g), len(g[0])
        if k >= r + c - 3:
            return r + c -2
        
        mem = {(0, 0):0}
        q, step = [(0, 0, 0)], 0
        
        while q:
            n = len(q)
            for _ in range(n):
                x, y, pre = q.pop(0)
                if pre > k: 
                    continue
                    
                if x == r - 1 and y == c - 1:
                    return step
                
                for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    nx, ny = x + i, y + j
                    if 0 <= nx < r and 0 <= ny < c:
                        nPre = pre + 1 if g[nx][ny] == 1 else pre
                        if nPre < mem.get((nx, ny), float("inf")):
                            q.append((nx, ny, nPre))
                            mem[(nx, ny)] = nPre
            step += 1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！