# 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:

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

## Examples

Example 1:

```python
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:

```text
left -> down -> left -> down -> right -> down -> right
```

The ball can stop at `[4, 4]`.

Answer:

```python
True
```

Example 2:

```python
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:

```python
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:

```text
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:

1. Pop a stopping cell.
2. If it equals `destination`, return `True`.
3. 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

```python
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:

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

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

```python
target = tuple(destination)
```

The four possible rolling directions are:

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

The BFS starts from `start`:

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

For each direction, we simulate rolling:

```python
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:

```python
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.

```python
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

```python
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 |