1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

solution

• 思路: bfs最短路径, 迭代时记录辅助信息来实现功能

class Solution:
    def __init__(self):
        self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m = len(grid)
        n = len(grid[0])

        queue = collections.deque()
        queue.append((0, 0, k, 0))
        visited = set()  # 注意, k是剩余可去掉障碍，也是判断重复的因素
        visited.add((0, 0, k))        

        while queue:
            for _ in range(len(queue)):
                i, j, num, steps = queue.popleft()

                if i == m - 1 and j == n - 1:
                    return steps  # 起点不算第一步

                for dir in self.dirs:
                    new_i = i + dir[0]
                    new_j = j + dir[1]                                    
            
                    if 0 <= new_i < m and 0 <= new_j < n:
                        if grid[new_i][new_j] == 1:
                            new_num = num - 1  # 注意: 必须新一个剩余障碍
                        else:
                            new_num = num

                        if new_num >= 0 and (new_i, new_j, new_num) not in visited:                                               
                            visited.add((new_i, new_j, new_num))
                            queue.append((new_i, new_j, new_num, steps+1))
        return -1

时间复杂度：O() 空间复杂度：O()