演算法練習 Leetcode 力扣 1293 Shortest Path in a Grid with Obstacles Elimination 解法

問題

題目在

解題思路

格子題,從左上到右下需要的最小步數。難點在給了個預算k,最多可以穿牆k次。找距離需要用BFS,不走回頭路就可以,比較簡單。但是這題在空間上是有可能走回頭路的,因為除了空間以外,還多了個狀態是已經穿牆幾次。放到queue裡面的應該是(坐標,穿牆次數)的tuple。所以關鍵在於不要把相同(坐標,穿牆次數)放queue里,不然會無法停止。

Python解法

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        rows, cols = len(grid), len(grid[0])
        
        def valid(cord):
            return 0 <= cord[0] < rows and 0 <= cord[1] < cols
        
        def nbs(cord):
            dirs = [
                (0,1),
                (0,-1),
                (1,0),
                (-1,0)
            ]
            
            new_cords = [ (cord[0] + dir[0], cord[1] + dir[1]) for dir in dirs]
            return list(filter(lambda x: valid(x), new_cords))
        
        
        def seen_to_grid(seen):
            grid = [[None for c in range(cols)] for r in range(rows)]
            for key in seen:
                cord, removed = key
                if grid[cord[0]][cord[1]] is None:
                    grid[cord[0]][cord[1]] = []
                grid[cord[0]][cord[1]].append(removed)
            print_grid(grid)
                
        
        def print_grid(grid):
            for row in grid:
                row_of_str = [str(col) for col in row]
                print('  '.join(row_of_str))
            print()
                        
        q = [((0,0), grid[0][0], 0)]
        seen = set()
        while q:
            cord, removed, dist = q.pop(0)
            seen_to_grid(seen)
            if removed > k or (cord, removed) in seen:
                continue
            seen.add((cord, removed))
            if cord == (rows-1, cols-1):
                return dist
            next_cords = nbs(cord)
            for next_cord in next_cords:
                q.append(
                    (next_cord, 
                     removed + grid[next_cord[0]][next_cord[1]], 
                     dist+1)
                )
        return -1                
            

                
        

Leave a Comment

Your email address will not be published.