# LeetCode 576: Out of Boundary Paths

## Problem Restatement

We are given an `m x n` grid and a ball starting at position `[startRow, startColumn]`.

On each move, the ball can move one cell in one of four directions:

```python
up, down, left, right
```

The ball may also move outside the grid. We can use at most `maxMove` moves.

Return the number of different paths that move the ball out of the grid boundary. Since the answer may be large, return it modulo `10^9 + 7`.

## Input and Output

| Item | Meaning |
|---|---|
| `m` | Number of rows |
| `n` | Number of columns |
| `maxMove` | Maximum number of moves allowed |
| `startRow` | Starting row of the ball |
| `startColumn` | Starting column of the ball |
| Output | Number of paths that leave the grid, modulo `10^9 + 7` |

Constraints:

| Constraint | Value |
|---|---|
| `m`, `n` | `1 <= m, n <= 50` |
| `maxMove` | `0 <= maxMove <= 50` |
| `startRow` | `0 <= startRow < m` |
| `startColumn` | `0 <= startColumn < n` |

## Examples

Example 1:

```python
m = 2
n = 2
maxMove = 2
startRow = 0
startColumn = 0
```

Output:

```python
6
```

The ball starts at the top-left corner. Some paths leave immediately by moving up or left. Other paths stay inside for one move and leave on the second move.

Example 2:

```python
m = 1
n = 3
maxMove = 3
startRow = 0
startColumn = 1
```

Output:

```python
12
```

The grid has only one row, so moving up or down exits the grid immediately.

## First Thought: Brute Force

A direct solution is to try every possible sequence of moves.

At each step, there are four choices:

```python
up, down, left, right
```

So with `maxMove` moves, the number of possible move sequences can be as large as:

```python
4^maxMove
```

Since `maxMove` can be `50`, this is far too large.

## Key Insight

Many paths reach the same state.

A state is determined by three values:

```python
(row, column, moves_left)
```

For example, if we are at cell `(1, 2)` with `5` moves left, the number of ways to eventually leave the grid is always the same. It does not matter how we arrived there.

So we can define:

```python
dp(row, col, moves_left)
```

as the number of paths that move the ball out of the grid, starting from `(row, col)` with `moves_left` moves remaining.

This gives us a recursive dynamic programming problem.

## Recurrence

If the ball is already outside the grid, then we found one valid path:

```python
return 1
```

If the ball is still inside the grid but no moves remain, then this path failed to leave:

```python
return 0
```

Otherwise, try the four possible moves:

```python
dp(row, col, moves_left)
=
dp(row + 1, col, moves_left - 1)
+ dp(row - 1, col, moves_left - 1)
+ dp(row, col + 1, moves_left - 1)
+ dp(row, col - 1, moves_left - 1)
```

Take the result modulo `10^9 + 7`.

## Algorithm

Use DFS with memoization.

1. Define a recursive function `dfs(row, col, moves_left)`.
2. If `(row, col)` is outside the grid, return `1`.
3. If `moves_left == 0`, return `0`.
4. If this state was already computed, return the cached value.
5. Recursively try all four directions.
6. Store the result in the cache.
7. Return `dfs(startRow, startColumn, maxMove)`.

## Correctness

We prove that `dfs(row, col, moves_left)` returns the number of valid paths that move the ball out of the grid from the given state.

If `(row, col)` is outside the grid, the path has already crossed the boundary. This contributes exactly one valid path, so returning `1` is correct.

If `(row, col)` is inside the grid and `moves_left == 0`, no more moves are allowed. Since the ball has not left the grid, this contributes no valid path, so returning `0` is correct.

For any inside cell with at least one move left, every valid path must begin with exactly one of the four possible moves. After that first move, the number of valid completions is exactly the value of `dfs` on the next cell with one fewer move. These four sets of paths are disjoint because they have different first moves. Therefore, summing the four recursive results counts every valid path exactly once.

Memoization does not change the value being computed. It only reuses the result for a state that has already been solved.

Therefore, `dfs(startRow, startColumn, maxMove)` returns the required answer.

## Complexity

Let:

```python
K = maxMove
```

There are at most:

```python
m * n * (K + 1)
```

states.

Each state tries four directions.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n * maxMove)` | Each state is computed once |
| Space | `O(m * n * maxMove)` | The memoization cache stores states |

## Implementation

```python
from functools import cache

class Solution:
    def findPaths(
        self,
        m: int,
        n: int,
        maxMove: int,
        startRow: int,
        startColumn: int,
    ) -> int:
        MOD = 1_000_000_007

        @cache
        def dfs(row: int, col: int, moves_left: int) -> int:
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1

            if moves_left == 0:
                return 0

            total = 0
            total += dfs(row + 1, col, moves_left - 1)
            total += dfs(row - 1, col, moves_left - 1)
            total += dfs(row, col + 1, moves_left - 1)
            total += dfs(row, col - 1, moves_left - 1)

            return total % MOD

        return dfs(startRow, startColumn, maxMove)
```

## Code Explanation

The constant:

```python
MOD = 1_000_000_007
```

is required because the number of paths can be very large.

The cached function:

```python
dfs(row, col, moves_left)
```

represents the number of ways to leave the grid from the current position with the given number of moves remaining.

This condition checks whether the ball has left the grid:

```python
if row < 0 or row >= m or col < 0 or col >= n:
    return 1
```

Once the ball leaves, we count that path immediately.

This condition checks whether we are stuck inside the grid:

```python
if moves_left == 0:
    return 0
```

If there are no moves left and the ball has not crossed the boundary, this path does not count.

Then we try all four directions:

```python
total += dfs(row + 1, col, moves_left - 1)
total += dfs(row - 1, col, moves_left - 1)
total += dfs(row, col + 1, moves_left - 1)
total += dfs(row, col - 1, moves_left - 1)
```

Each recursive call uses one move.

Finally, we return:

```python
return total % MOD
```

The cache ensures that each state is solved only once.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findPaths(2, 2, 2, 0, 0) == 6
    assert s.findPaths(1, 3, 3, 0, 1) == 12
    assert s.findPaths(1, 1, 0, 0, 0) == 0
    assert s.findPaths(1, 1, 1, 0, 0) == 4
    assert s.findPaths(2, 3, 1, 0, 1) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `2 x 2`, start at corner, `2` moves | Matches the sample case |
| `1 x 3`, start in middle, `3` moves | Handles one-row grids |
| `1 x 1`, `0` moves | Cannot leave without moving |
| `1 x 1`, `1` move | Any of four moves exits |
| `2 x 3`, top edge, `1` move | Only moving up exits immediately |