0576. Out of Boundary Paths

---

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent four cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0

Output: 6

Example 2:

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1

Output: 12

Constraints:

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow <= m
• 0 <= startColumn <= n

---

解法1

DFS搜索,用三维数组保存在点(x,y)还留有z步的时候,可能的路径数.

class Solution {
    
    int mod = 1000000007;
    int[] move = new int[]{0, 1, 0, -1, 0};
    
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[][][] memo = new int[m][n][maxMove + 1];
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                Arrays.fill(memo[i][j], -1);
        
        return helper(m, n, maxMove, startRow, startColumn, memo);
    }
    
    private int helper(int m, int n, int left, int x, int y, int[][][] memo){
        // 如果出界, 那么返回结果1(当前移动方式可以出界)
        if(x < 0 || y < 0 || x == m || y == n)
            return 1;
        
        // 如果剩余移动次数为0, 那么返回0(即当前移动方式无法出界)
        if(left == 0)
            return 0;
        
        // 如果之前在剩余left步时到达过点(x, y),并且可以出界, 那么直接返回上次计算过的值
        // 因为储存的是从点(x, y)开始可能出界的所有路径的个数, 第一次之后访问的时候, 可以直接拿来用
        if(memo[x][y][left] > 0)
            return memo[x][y][left];
        
        int res = 0;
        for(int k = 0; k < 4; k++)
            res =  (res + helper(m, n, left - 1, x + move[k], y + move[k + 1], memo)) % mod;
        
        memo[x][y][left] = res;
        return res;
    }
}