576. Out of Boundary Paths

发表于 | 分类于

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

Example 2:

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

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

解法1：

比较喜欢memorization的这个解法。
最直观的思路就是对于每一个位置，用递归像4个方向搜索是否能到边界之外。如果可以则返回1.
而每一个节点的数值是所有方向相加。但对于每一个位置(i,j)，和一定剩余的步数k, 这个组合在搜索的过程中会出现多次，所以用一个矩阵来记录下中间结果。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    private int M=1000000007;
    public int findPaths(int m, int n, int N, int i, int j) {
        int[][][] memo = new int[m][n][N + 1];
        for (int k = 0; k < m; k++) {
            for (int l = 0; l < n; l++) {
                for (int p = 0; p <= N; p++) {
                    memo[k][l][p] = -1;
                }
            }
        }
        return helper(m, n, N, i, j, memo);
    }
    private int helper(int m, int n, int N, int i, int j, int[][][] memo) {
        if (i == m || j == n || i < 0 || j < 0) {
            return 1;
        }
        if (N == 0) {
            return 0;
        }
        if (memo[i][j][N] != -1) {
            return memo[i][j][N];
        }
        memo[i][j][N] = ((helper(m, n, N - 1, i + 1, j, memo) + helper(m, n, N - 1, i - 1, j, memo))%M + (helper(m, n, N - 1, i, j + 1, memo) + helper(m, n, N - 1, i, j - 1, memo))%M)%M;
        return memo[i][j][N];
    }
}