LeetCode 505: The Maze II

Problem Restatement

We are given a maze represented as a grid.

A ball starts at position start.

The goal is to reach position destination.

The ball does not move one cell at a time.

Instead, once the ball starts moving in a direction, it keeps rolling until it hits a wall. Only then can it choose another direction.

We need to return the shortest distance traveled by the ball to stop exactly at destination.

If the destination cannot be reached, return -1.

The official problem defines the distance as the number of empty spaces traveled by the ball, excluding the starting cell and including the destination cell. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def shortestDistance(
        self,
        maze: List[List[int]],
        start: List[int],
        destination: List[int],
    ) -> int:
        ...

Examples

Example:

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]

From (0,4):

• roll left
• roll down
• continue until walls stop movement

The shortest valid rolling path has total distance:

12

A key detail is that the ball cannot stop early.

If the ball is rolling, it must continue until blocked by a wall.

First Thought: Use BFS

In a normal grid shortest-path problem, BFS is often correct because every move costs the same.

However, this maze behaves differently.

A single move can travel many cells.

For example:

roll up  -> distance 5
roll left -> distance 1

So edges have different weights.

Regular BFS does not correctly handle weighted shortest paths.

Problem With BFS

BFS assumes every edge has equal cost.

Here, rolling distances vary.

A path with fewer rolls may still have a larger total distance.

So we need an algorithm for weighted shortest paths.

This is exactly the use case for Dijkstra’s algorithm.

Key Insight

Treat every stopping position as a graph node.

From each node:

• roll in four directions
• continue until hitting a wall
• measure the traveled distance

That creates weighted edges.

We then run Dijkstra’s algorithm:

Whenever we find a shorter path to a stopping position, we update it and push it into the heap.

Algorithm

Let:

m = len(maze)
n = len(maze[0])

Create a distance matrix initialized to infinity:

dist = [[float("inf")] * n for _ in range(m)]

Set the start distance to 0.

Use a min heap:

heap = [(0, start_row, start_col)]

Each heap entry contains:

(current_distance, row, col)

While the heap is not empty:

1. Pop the smallest distance state.
2. If this state is outdated, skip it.
3. For each direction:
   • roll until hitting a wall
   • count traveled cells
4. If the new total distance is better:
   • update dist
   • push the new state into the heap

Finally:

• return the destination distance
• or -1 if unreachable

Correctness

Each stopping position in the maze is treated as a graph node.

Rolling from one stopping position to another produces an edge whose weight equals the traveled distance.

All edge weights are nonnegative.

Dijkstra’s algorithm is correct for graphs with nonnegative edge weights.

The heap always extracts the currently known shortest unprocessed distance.

When a position (r, c) is processed with distance d, no shorter path to (r, c) can exist later.

For every direction, the algorithm computes the exact stopping position and traveled distance produced by rolling until a wall.

If a newly discovered path improves the known distance for that stopping position, the distance table and heap are updated.

Thus the algorithm eventually computes the shortest possible rolling distance from the start to every reachable stopping position.

Therefore the value returned for destination is the correct shortest distance. If the destination remains unreachable, returning -1 is correct.

Complexity

The rolling step itself can travel across rows or columns, but the asymptotic complexity is still acceptable for the problem constraints.

Implementation

from typing import List
import heapq

class Solution:
    def shortestDistance(
        self,
        maze: List[List[int]],
        start: List[int],
        destination: List[int],
    ) -> int:
        m = len(maze)
        n = len(maze[0])

        dist = [[float("inf")] * n for _ in range(m)]

        start_row, start_col = start
        dist[start_row][start_col] = 0

        heap = [(0, start_row, start_col)]

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        while heap:
            current_dist, row, col = heapq.heappop(heap)

            if current_dist > dist[row][col]:
                continue

            for dr, dc in directions:
                nr = row
                nc = col
                steps = 0

                while (
                    0 <= nr + dr < m
                    and 0 <= nc + dc < n
                    and maze[nr + dr][nc + dc] == 0
                ):
                    nr += dr
                    nc += dc
                    steps += 1

                new_dist = current_dist + steps

                if new_dist < dist[nr][nc]:
                    dist[nr][nc] = new_dist
                    heapq.heappush(heap, (new_dist, nr, nc))

        dest_row, dest_col = destination

        if dist[dest_row][dest_col] == float("inf"):
            return -1

        return dist[dest_row][dest_col]

Code Explanation

The distance table stores the best known distance to each cell:

dist = [[float("inf")] * n for _ in range(m)]

The starting position has distance 0:

dist[start_row][start_col] = 0

The heap stores states ordered by shortest distance:

heap = [(0, start_row, start_col)]

When processing a state, outdated heap entries are ignored:

if current_dist > dist[row][col]:
    continue

For each direction, the ball keeps rolling:

while (
    0 <= nr + dr < m
    and 0 <= nc + dc < n
    and maze[nr + dr][nc + dc] == 0
):

The loop stops only when the next move would hit a wall or boundary.

The traveled distance is:

new_dist = current_dist + steps

If this improves the best known distance:

if new_dist < dist[nr][nc]:

we update the table and push the new state into the heap.

At the end, if the destination distance is still infinity, the destination was unreachable.

Testing

def test_shortest_distance():
    s = Solution()

    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],
    ]

    assert s.shortestDistance(
        maze,
        [0, 4],
        [4, 4],
    ) == 12

    assert s.shortestDistance(
        maze,
        [0, 4],
        [3, 2],
    ) == -1

    maze2 = [
        [0, 0],
        [0, 0],
    ]

    assert s.shortestDistance(
        maze2,
        [0, 0],
        [1, 1],
    ) == 2

    maze3 = [
        [0],
    ]

    assert s.shortestDistance(
        maze3,
        [0, 0],
        [0, 0],
    ) == 0

    print("all tests passed")

Test meaning: