The Maze II

Intuition

The ball does not move one cell at a time, it slides until a wall stops it, so the graph's nodes are the stopping positions and the edges are complete rolls whose weight is the number of cells crossed. Those weights are additive and non-negative, so Dijkstra over stopping positions yields the minimum total distance to stop at each cell. A min-heap always settles the closest reachable stop first, so the first time the destination is popped we already have its shortest stopping distance. If the destination is never settled, the ball can never rest there and the answer is -1. This is exactly single-source shortest path where generating a neighbor means rolling until a wall.

Algorithm walkthrough

1. 1Keep a 2D dist grid of shortest rolling distances, set the start cell to 0, and push (0, startRow, startCol) onto a min-heap.
2. 2Pop the cell with the smallest rolled distance; if it is the destination, return that distance.
3. 3Skip stale entries whose stored distance is smaller than the popped value.
4. 4For each of the four directions, roll the ball cell by cell until the next cell is a wall or out of bounds, counting the empty cells crossed.
5. 5If reaching that stopping cell via the current path is shorter, update its distance and push the new stopping state.
6. 6When the heap empties without settling the destination, return -1.

Implementation

import heapq
from typing import List


class Solution:
    def shortestDistance(
        self, maze: List[List[int]], start: List[int], destination: List[int]
    ) -> int:
        m, n = len(maze), len(maze[0])
        dist = [[float("inf")] * n for _ in range(m)]
        dr, dc = destination
        dist[start[0]][start[1]] = 0
        heap = [(0, start[0], start[1])]
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while heap:
            d, r, c = heapq.heappop(heap)
            if r == dr and c == dc:
                return d
            if d > dist[r][c]:
                continue
            for dx, dy in dirs:
                nr, nc, steps = r, c, 0
                while (
                    0 <= nr + dx < m
                    and 0 <= nc + dy < n
                    and maze[nr + dx][nc + dy] == 0
                ):
                    nr += dx
                    nc += dy
                    steps += 1
                if d + steps < dist[nr][nc]:
                    dist[nr][nc] = d + steps
                    heapq.heappush(heap, (d + steps, nr, nc))

        return -1