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

dp[k][i][j]代表從(i, j)開始走k步超出邊界的總數量。走k步超出邊界的路徑總合等於周圍四個位置走k-1步超出邊界的路徑總和。

// 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];
}

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

// 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;
}

688. Knight Probability in Chessboard