505. The Maze II - cocoder39/coco39_LC GitHub Wiki

505. The Maze II

Dijkstra

don't miss distance + move < dist[(newRow, newCol)]

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        m, n = len(maze), len(maze[0])
        dist = {}
        
        pq = [(0, start[0], start[1])]
        
        res = float("inf")
        while pq:
            distance, row, col = heapq.heappop(pq)
            
            if row == destination[0] and col == destination[1]:
                return distance
            
            for dx, dy in DIRECTIONS:
                newRow, newCol, move = row, col, 0
                while 0 <= newRow+dx < m and 0 <= newCol+dy < n and maze[newRow+dx][newCol+dy] == 0:
                    newRow += dx
                    newCol += dy
                    move += 1
                
                if (newRow, newCol) not in dist or distance + move < dist[(newRow, newCol)]:
                    dist[(newRow, newCol)] = distance + move
                    heapq.heappush(pq, (distance + move, newRow, newCol))
        
        return -1