> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/576-out-of-boundary-paths.md).

# 576     Out of Boundary Paths

## 576. [Out of Boundary Paths](https://leetcode.com/problems/out-of-boundary-paths/description/)

## 1. Question

There is an **m** by **n** grid with a ball. Given the start coordinate**(i,j)**of the ball, you can move the ball to **adjacent** cell or cross the grid boundary in four directions (up, down, left, right). However, you can **at most** move **N** times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109+ 7.

**Example 1:**

```
Input:
m = 2, n = 2, N = 2, i = 0, j = 0

Output:
6
```

**Example 2:**

```
Input:
m = 1, n = 3, N = 3, i = 0, j = 1

Output:
12
```

**Note:**

1. Once you move the ball out of boundary, you cannot move it back.
2. The length and height of the grid is in range \[1,50].
3. N is in range \[0,50].

## 2. Implementation

**(1) DP**

思想: 这道题要我们求出从(i, j)出发，有多少种路径可以让我们把球移除边界. 利用动态规划的思想，dp\[i]\[j]\[k]表示从(i,j)出发,走k步可以走出边界的路径总数，显然dp\[i]\[j]\[k]的状态取决于它四周(上下左右)的状态影响，

即dp\[i]\[j]\[k] = dp\[i - 1]\[j]\[k - 1] + dp\[i + 1]\[j]\[k - 1] + dp\[i]\[j - 1]\[k - 1] + dp\[i]\[j + 1]\[k - 1], base case为当(i,j)在边界位置时, dp\[i]\[j]\[k] = 1，因为在边界上只需要1步可以走出边界

```java
class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        long[][][] dp = new long[m][n][N + 1];
        int M = 1000000007;
        for (int k =1; k <= N; k++) {
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    long up = x == 0 ? 1 : dp[x - 1][y][k - 1];
                    long down = x == m - 1 ? 1 : dp[x + 1][y][k - 1];
                    long left = y == 0 ? 1 : dp[x][y - 1][k - 1];
                    long right = y == n - 1 ? 1 : dp[x][y + 1][k - 1];

                    dp[x][y][k] = (up + down + left + right) % M;
                }
            }
        }
        return (int)dp[i][j][N];
    }
}
```

## 3. Time & Space Complexity

**DP**: 时间复杂度O(m \* n \* N), 空间复杂度O(m \* n \* N)