The Maze II Python Solution with Tests

lcpy gen -n 505   # by problem number
lcpy gen -s the_maze_ii   # by problem name

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: -1
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: -1

import heapq


class Solution:
    # Time: O(m * n * max(m, n) * log(m * n))
    # Space: O(m * n)
    def shortest_distance(
        self, maze: list[list[int]], start: list[int], destination: list[int]
    ) -> int:
        m, n = len(maze), len(maze[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        goal = (destination[0], destination[1])
        dist = {(start[0], start[1]): 0}
        heap = [(0, start[0], start[1])]
        while heap:
            d, r, c = heapq.heappop(heap)
            if (r, c) == goal:
                return d
            if d > dist.get((r, c), 10**9):
                continue
            for dr, dc in dirs:
                nr, nc, steps = r, c, 0
                while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
                    nr += dr
                    nc += dc
                    steps += 1
                if d + steps < dist.get((nr, nc), 10**9):
                    dist[(nr, nc)] = d + steps
                    heapq.heappush(heap, (d + steps, nr, nc))
        return -1