> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Out of Boundary Paths Python Solution

> Tested Python solution for LeetCode 576 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 576, [Medium](/catalog/medium). Topics: [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/out-of-boundary-paths/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 576   # by problem number
lcpy gen -s out_of_boundary_paths   # by problem name
```

## Problem

There is an `m x n` grid with a ball. The ball is initially at the position `[startRow, startColumn]`. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply **at most** `maxMove` moves to the ball.

Given the five integers `m`, `n`, `maxMove`, `startRow`, `startColumn`, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it **modulo** `10^9 + 7`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_1.png)

```
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
```

![Example 2](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_2.png)

```
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12
```

### Constraints

* 1 \<= m, n \<= 50
* 0 \<= maxMove \<= 50
* 0 \<= startRow \< m
* 0 \<= startColumn \< n

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/out_of_boundary_paths/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/out_of_boundary_paths/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(max_move * m * n)
    # Space: O(m * n)
    def find_paths(
        self,
        m: int,
        n: int,
        max_move: int,
        start_row: int,
        start_column: int,
    ) -> int:
        mod = 1_000_000_007
        # dp[r][c]: number of paths currently at cell (r, c) inside the grid.
        dp = [[0] * n for _ in range(m)]
        dp[start_row][start_column] = 1
        paths = 0
        for _ in range(max_move):
            nxt = [[0] * n for _ in range(m)]
            for row in range(m):
                for col in range(n):
                    count = dp[row][col]
                    if not count:
                        continue
                    for n_row, n_col in (
                        (row + 1, col),
                        (row - 1, col),
                        (row, col + 1),
                        (row, col - 1),
                    ):
                        if 0 <= n_row < m and 0 <= n_col < n:
                            nxt[n_row][n_col] = (nxt[n_row][n_col] + count) % mod
                        else:
                            paths = (paths + count) % mod
            dp = nxt
        return paths
```

## Complexity

| Time | Space |
| - | - |
| O(max\_move \* m \* n) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.