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

# 576. Out of Boundary Paths

<https://leetcode.com/problems/out-of-boundary-paths/description/>

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

```

**Example 2:**

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

```

**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].

{% hint style="info" %}
dp\[k]\[i]\[j]代表從(i, j)開始走k步超出邊界的總數量。走k步超出邊界的路徑總合等於周圍四個位置走k-1步超出邊界的路徑總和。
{% endhint %}

```cpp
// Bottom-Up Dynamic Programming
int findPaths(int m, int n, int N, int i, int j) { // time: O(N * m * n); space: O(m * n)
    // dp[k][i][j] means the total number of ways to go beyond boundary starting from (i, j) after k steps
    // dp[k][i][j] = the total ways to go beyond the boundary from the four neighboring locations of (i, j) with k-1 steps
    vector<vector<vector<int> > > dp(N + 1, vector<vector<int> > (m, vector<int>(n, 0)));
    for (int k = 1; k <= N; ++k) {
        for (int x = 0; x < m; ++x) {
            for (int y = 0; y < n; ++y) {
                long long up = (x == 0) ? 1 : dp[k - 1][x - 1][y];
                long long down = (x == m - 1) ? 1 : dp[k - 1][x + 1][y];
                long long left = (y == 0) ? 1 : dp[k - 1][x][y - 1];
                long long right = (y == n - 1) ? 1 : dp[k - 1][x][y + 1];
                dp[k][x][y] = (up + down + left + right) % 1000000007;
            }
        }
    }
    return dp[N][i][j];
}
```

{% hint style="info" %}
dp\[k]\[i]\[j]代表走了k步走到(i, j)位置的總路徑數量，定義和第一個解法不同。因為dp\[k]\[i]\[j]只會跟dp\[k - 1]\[i]\[j]有關，所以可以只保存一個2D table每一輪k loop後更新它。
{% endhint %}

```cpp
// Similar-BFS DP
int findPaths(int m, int n, int N, int i, int j) { // time: O(N * m * n); space: O(m * n)
    int res = 0;
    vector<vector<int> > dp(m, vector<int>(n, 0));
    dp[i][j] = 1;
    vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
    for (int k = 0; k < N; ++k) {
        vector<vector<int>> t(m, vector<int>(n, 0));
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                for (vector<int>& dir : dirs) {
                    int x = r + dir[0], y = c + dir[1];
                    if (x < 0 || x >= m || y < 0 || y >= n) {
                        res = (res + dp[r][c]) % 1000000007;
                    } else {
                        t[x][y] = (t[x][y] + dp[r][c]) % 1000000007;
                    }
                }
            }
        }
        dp = t;
    }
    return res;
}
```

{% content-ref url="/pages/-L\_tstoCERzVxJKHZ2SY" %}
[688. Knight Probability in Chessboard](/practice-of-algorithm-problems/dynamic-programming/688.-knight-probability-in-chessboard.md)
{% endcontent-ref %}