1293. Shortest Path in a Grid with Obstacles Elimination

Loading...LeetCode

BFS基础上用了堆结构，永远找当下使用步数最少的路线继续走。

class Solution:
    def validNext(self, x, y, m, n):
        return [(i, j) for (i, j) in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] if (0 <= i < m) and (0 <= j < n)]
        
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        visited = set()
        visited.add((0, 0, k))
        
        queue = [(0, (0, 0, k))]
        
        while queue:
            steps, (x, y, k) = heapq.heappop(queue)
            
            # 主要是这一步省了时间
            # 当发现距离终点(m-1,n-1)的距离已经小于等于k的时候，就说明直线奔过去就到了
            # 所以直接返回直线步数总和，不需要继续往下搜索了
            if (m-1-x) + (n-1-y) <= k: 
                return steps + (m-1-x) + (n-1-y)
                
            for x, y in self.validNext(x, y, m, n):
                if k - grid[x][y] >= 0:
                    state = (x, y, k-grid[x][y])
                    if state not in visited:
                        heapq.heappush(queue, (steps + 1, state))
                        visited.add(state)
        return -1