1293. Shortest Path in a Grid with Obstacles Elimination

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

题目解释

你会得到一个m*n大小的表格，表格填满了0和1，0和1分别代表通道和障碍物

你还会得到一个数字k，k代表你你可以排除掉几个障碍物

请回传从最左上角(0,0)到最右下角(m-1, n-1)最短须走几步，如果无法到达则回传-1

example

解法

这题想不到明确的解法，所以直接找其他人的答案，其中一篇解释得很清楚

所以今天就大致翻译他给的key process

• 每一步都要确认是否到达终点，如果不是就继续搜寻
• 每一格的下一步都有4个方向，要确认每一步是否可行(是否到达边界、是否还有多余的k能去掉障碍物)
• 重复这个步骤直到到达终点，若是k耗尽且未抵达终点则回传-1

程序码

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        
        if k >= m + n - 2: return m + n - 2
        # 如果 k > 最短路径的步数，就能直直的走过去
        
        q = deque([(0, 0, 0, k)]) # (row, column)目前位置, 累积步数, 剩余的k
        visted = set() # 纪录走过的路，避免走回头路
        
        direct = [(0,1), (1,0), (0,-1), (-1,0)]
        # 四个方向
        
        while q:
            
            row, col, step, k = q.popleft()
            
            if row == m-1 and col == n-1:
            # 到达终点
                return step
            
            for i, j in direct:
                
                if 0 <= row + i and row + i < m and 0 <= col + j and col + j < n and (row + i, col + j, k) not in visted:
                # 确认是否为边界，是否为走过的格子
                    
                    if grid[row + i][col + j] == 1 and k > 0: #遇到障碍物
                        q.append((row + i, col + j, step + 1, k - 1))
                        visted.add((row + i, col + j, k))
                    if grid[row + i][col + j] == 0: #有通道
                        q.append((row + i, col + j, step + 1, k))
                        visted.add((row + i, col + j, k))
        return -1