Leetcode 1293:网格中的最短路径(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1293:网格中的最短路径(超详细的解法!!!)

in leetcode with 0 comment

给你一个 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
解释:
我们至少需要消除两个障碍才能找到这样的路径。 

提示:

解题思路

最短路经问题直接使用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

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

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses