# 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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/576.-out-of-boundary-paths.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.