LeetCode 499: The Maze III

Problem Restatement

We are given a maze represented by a 2D grid.

A ball starts at ball.

There is also a hole at hole.

The ball can roll in four directions:

Once the ball starts rolling, it keeps moving in that direction until one of two things happens:

1. It hits a wall and stops before the wall.
2. It reaches the hole and falls in.

We need to return the path string that makes the ball fall into the hole with the shortest distance.

Distance means the number of empty cells traveled from the start position, excluding the start cell and including the hole.

If several paths have the same shortest distance, return the lexicographically smallest path string.

If the hole cannot be reached, return:

"impossible"

Input and Output

Function shape:

def findShortestWay(
    maze: list[list[int]],
    ball: list[int],
    hole: list[int],
) -> str:
    ...

Examples

Example 1:

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],
]
ball = [4, 3]
hole = [0, 1]

There are two shortest ways to reach the hole:

lul
ul

Both have distance 6.

Lexicographically:

lul < ul

because l < u.

Answer:

"lul"

Example 2:

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],
]
ball = [4, 3]
hole = [3, 0]

The ball cannot stop at or fall into the hole.

Answer:

"impossible"

First Thought: Use Normal BFS

In a normal maze, each move costs 1.

Then BFS works because every edge has the same weight.

Here, one move can roll many cells.

For example, rolling left may travel 1 cell, while rolling up may travel 4 cells.

So edges have different weights.

That means normal BFS by number of rolls is not enough. We need shortest distance by number of cells traveled.

Key Insight

Treat every stopping cell as a graph node.

From a node, the ball can roll in four directions. Each roll produces:

This is a shortest path problem with weighted edges.

So use Dijkstra.

The priority queue stores:

(distance, path, row, col)

Python compares tuples from left to right.

That means the heap automatically prioritizes:

1. Smaller distance.
2. Lexicographically smaller path.

This matches the problem exactly.

Rolling Until Wall or Hole

When trying a direction, we repeatedly move while the next cell is valid and not a wall.

But we must stop early if we reach the hole.

For example:

while next cell is open:
    move one step
    if current cell is hole:
        break

This is different from LeetCode 490, where passing through the destination did not count.

In this problem, once the ball reaches the hole, it falls in immediately.

Algorithm

Use a min-heap.

Initialize:

heap = [(0, "", ball_row, ball_col)]

Maintain a dictionary:

best[(row, col)] = (distance, path)

where best stores the best known way to reach each cell.

While the heap is not empty:

1. Pop the state with smallest (distance, path).
2. If this cell is the hole, return path.
3. If this state is worse than the best recorded state, skip it.
4. Try rolling in directions in lexicographic order:
   • d
   • l
   • r
   • u
5. For each roll:
   • compute the stopping cell or hole
   • compute the new distance
   • compute the new path
   • relax the state if it is better

If the heap ends without reaching the hole, return "impossible".

Correctness

Each state in the heap represents a real path the ball can take to a cell, with its traveled distance and path string.

For every popped state, the algorithm simulates all legal rolls from that cell. Each simulated roll exactly follows the problem rule: the ball moves until it hits a wall or falls into the hole.

The priority queue orders states by (distance, path). Therefore, the first time the hole is popped, it has the smallest possible distance among all reachable paths. If another path has the same distance but a lexicographically smaller path string, that path would have been popped earlier because tuple ordering compares the path after the distance.

The best dictionary prevents expanding states that are worse than a previously discovered state for the same cell. A state is better if it has a smaller distance, or the same distance with a smaller path string.

Dijkstra’s algorithm is valid here because all roll costs are positive. Therefore, once the hole is popped from the heap, no later path can improve it.

Thus the returned path is the shortest possible path to the hole, with lexicographic tie-breaking handled correctly.

Complexity

Let m be the number of rows and n be the number of columns.

Implementation

import heapq

class Solution:
    def findShortestWay(
        self,
        maze: list[list[int]],
        ball: list[int],
        hole: list[int],
    ) -> str:
        rows = len(maze)
        cols = len(maze[0])

        hole_row, hole_col = hole

        directions = [
            ("d", 1, 0),
            ("l", 0, -1),
            ("r", 0, 1),
            ("u", -1, 0),
        ]

        start = (ball[0], ball[1])
        heap = [(0, "", start[0], start[1])]
        best = {start: (0, "")}

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

            if (row, col) == (hole_row, hole_col):
                return path

            if best[(row, col)] < (dist, path):
                continue

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

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

                    if (nr, nc) == (hole_row, hole_col):
                        break

                new_dist = dist + steps
                new_path = path + ch
                state = (nr, nc)

                if state not in best or (new_dist, new_path) < best[state]:
                    best[state] = (new_dist, new_path)
                    heapq.heappush(heap, (new_dist, new_path, nr, nc))

        return "impossible"

Code Explanation

The direction order is chosen lexicographically:

directions = [
    ("d", 1, 0),
    ("l", 0, -1),
    ("r", 0, 1),
    ("u", -1, 0),
]

The heap stores distance first, then path:

heap = [(0, "", start[0], start[1])]

This gives us shortest distance first and lexicographically smallest path on ties.

The best map stores the best known (distance, path) for each cell:

best = {start: (0, "")}

When a heap state is outdated, skip it:

if best[(row, col)] < (dist, path):
    continue

Rolling continues while the next cell is inside the grid and open:

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

After each one-cell movement, we check whether the ball reached the hole:

if (nr, nc) == (hole_row, hole_col):
    break

This matters because the ball falls into the hole immediately.

If the new state is better, push it into the heap:

if state not in best or (new_dist, new_path) < best[state]:

If no path reaches the hole:

return "impossible"

Testing

def run_tests():
    s = Solution()

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

    assert s.findShortestWay(maze, [4, 3], [0, 1]) == "lul"
    assert s.findShortestWay(maze, [4, 3], [3, 0]) == "impossible"

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

    assert s.findShortestWay(maze2, [2, 0], [0, 2]) == "ru"

    maze3 = [
        [0, 0],
        [0, 0],
    ]

    assert s.findShortestWay(maze3, [0, 0], [1, 1]) == "dr"

    print("all tests passed")

run_tests()

Test meaning: