LeetCode 490: The Maze

Problem Restatement

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

Each cell has one of two values:

Value	Meaning
`0`	Empty space
`1`	Wall

A ball starts at start.

The ball can roll in four directions:

Direction
Up
Down
Left
Right

But the ball does not move one cell and stop. Once it starts rolling in a direction, it keeps rolling until it hits a wall. It stops immediately before the wall.

We need to return true if the ball can stop exactly at destination. Otherwise, return false.

The important detail is “stop exactly.” Passing through the destination while rolling does not count. The ball must end a roll there.

Input and Output

Item	Meaning
Input	`maze`, `start`, `destination`
Maze value `0`	Open cell
Maze value `1`	Wall
Output	`True` if the ball can stop at `destination`, otherwise `False`
Movement rule	The ball keeps rolling until blocked

Function shape:

def hasPath(maze: list[list[int]], start: list[int], destination: list[int]) -> bool:
    ...

Examples

Example 1:

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]

One valid route is:

left -> down -> left -> down -> right -> down -> right

The ball can stop at [4, 4].

Answer:

True

Example 2:

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]

The ball may pass through [3, 2], but it cannot stop there.

Answer:

False

First Thought: Normal Grid Search

A normal maze problem often lets us move one cell at a time.

Then we could run BFS or DFS like this:

from current cell:
    try the four adjacent cells

But this problem has different movement.

From a cell, choosing a direction may move the ball many cells until it hits a wall.

So the graph nodes should not be every step of movement. The useful nodes are the cells where the ball can stop.

Key Insight

Treat each stopping position as a graph node.

From one stopping position, we try rolling in each of the four directions.

The next node is the cell where the ball stops after rolling as far as possible in that direction.

For example, if the ball is at (row, col) and rolls right, we repeatedly move right while the next cell is inside the maze and open.

When the next cell is a wall or outside the maze, the current cell is the stopping point.

Then BFS or DFS can explore these stopping points.

Algorithm

Use BFS.

Initialize a queue with the start cell.

Mark the start cell as visited.

While the queue is not empty:

Pop a stopping cell.
If it equals destination, return True.
For each of the four directions:
- Roll until blocked.
- Get the final stopping cell.
- If this stopping cell has not been visited, mark it and add it to the queue.

If BFS finishes without reaching the destination, return False.

Correctness

The ball can only choose a new direction after it stops. Therefore, every meaningful state in the search is a stopping cell.

The BFS starts from the initial stopping cell, start.

For each visited stopping cell, the algorithm simulates all four legal rolls exactly as the rules require. Each roll produces the next stopping cell that the ball can reach in one move.

So every edge explored by BFS corresponds to one valid ball movement.

Conversely, every valid movement from a stopping cell is considered by one of the four direction simulations. Therefore, BFS explores every stopping cell reachable from start.

If the algorithm returns True, then it found destination as a reachable stopping cell, so the ball can stop there.

If the algorithm returns False, then all reachable stopping cells were explored and none was destination, so the ball cannot stop at the destination.

Complexity

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

Metric	Value	Why
Time	`O(m * n * max(m, n))`	Each cell can be visited as a stopping cell, and each roll may scan across a row or column
Space	`O(m * n)`	The queue and visited set may store many cells

Implementation

from collections import deque

class Solution:
    def hasPath(
        self,
        maze: list[list[int]],
        start: list[int],
        destination: list[int],
    ) -> bool:
        rows = len(maze)
        cols = len(maze[0])

        target = tuple(destination)

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

        queue = deque([tuple(start)])
        visited = {tuple(start)}

        while queue:
            row, col = queue.popleft()

            if (row, col) == target:
                return True

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

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

                if (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc))

        return False

Code Explanation

We store maze dimensions:

rows = len(maze)
cols = len(maze[0])

The destination is converted to a tuple so it can be compared with queue states:

target = tuple(destination)

The four possible rolling directions are:

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

The BFS starts from start:

queue = deque([tuple(start)])
visited = {tuple(start)}

For each direction, we simulate rolling:

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

This stops only when the next cell would be invalid or blocked.

Then (nr, nc) is the stopping cell.

If we have not visited it before, add it to BFS:

if (nr, nc) not in visited:
    visited.add((nr, nc))
    queue.append((nr, nc))

If all reachable stopping cells are exhausted, return False.

DFS Implementation

The same idea can be written with DFS.

class Solution:
    def hasPath(
        self,
        maze: list[list[int]],
        start: list[int],
        destination: list[int],
    ) -> bool:
        rows = len(maze)
        cols = len(maze[0])
        target = tuple(destination)
        visited = set()

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

        def dfs(row: int, col: int) -> bool:
            if (row, col) == target:
                return True

            if (row, col) in visited:
                return False

            visited.add((row, col))

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

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

                if dfs(nr, nc):
                    return True

            return False

        return dfs(start[0], start[1])

Testing

def run_tests():
    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.hasPath(maze, [0, 4], [4, 4]) is True
    assert s.hasPath(maze, [0, 4], [3, 2]) is False
    assert s.hasPath([[0]], [0, 0], [0, 0]) is True

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

    assert s.hasPath(maze2, [0, 0], [2, 2]) is True

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Example destination `[4, 4]`	Reachable stopping point
Example destination `[3, 2]`	May pass through, but cannot stop there
Single cell	Start already equals destination
Small open maze	Checks multiple rolling directions