iT邦幫忙

2021 iThome 鐵人賽

DAY 25
0
自我挑戰組

每日LeetCode解題紀錄系列 第 25

LeetCode解題 Day25

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分別代表通道和障礙物

你還會得到一個數字kk代表你你可以排除掉幾個障礙物

請回傳從最左上角(0,0)到最右下角(m-1, n-1)最短須走幾步,如果無法到達則回傳-1

example

https://i.imgur.com/A8JqmFc.png


解法

這題想不到明確的解法,所以直接找其他人的答案,其中一篇解釋得很清楚

所以今天就大致翻譯他給的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

上一篇
LeetCode解題 Day24
下一篇
LeetCode解題 Day26
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言