Problem

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:

思路一（纯dfs）

• 因为这个路径能够原路返回绕回去， 所以不需要backtrack

    public int findPaths(int m, int n, int N, int i, int j) {
        return helper(m, n, N, i, j);
    }

    // 因为路径可以绕回去，所以不需要backtrack
    private int helper(int m, int n, int N, int i, int j) {
        if(i==m || j==n || i<0 ||j<0)
            return 1;
        if(N == 0)
            return 0;

        return helper(m, n, N - 1, i + 1, j) +
                helper(m, n, N - 1, i, j + 1) +
                helper(m, n, N - 1, i - 1, j) +
                helper(m, n, N - 1, i, j - 1);
    }

优化

• 将函数中的变量作为索引，存在数组中
• 因为有三个变量， N， i，j，所以开一个三维数组
• 由于担心每次的dfs结果过大， 每次相加后都需要mod(10^9 + 7)
• dfs之前必须添加判断当前坐标距离边界的距离在N步内， 否则没有结果，而且会TLE

    public int findPaths(int m, int n, int N, int i, int j) {
        return helper(m, n, N, i, j, new int[m][n][N + 1]) % 1000000007;
    }

    // 因为路径可以绕回去，所以不需要backtrack
    private int helper(int m, int n, int N, int i, int j, int[][][] dp) {
        if(i==m || j==n || i<0 ||j<0)
            return 1;
        // 必须要加这个判断，否则仍然TLE
        if (i - N >= 0 && i + N < m && j - N >=0 && j + N < n)
            return 0;
        if(N == 0)
            return 0;

        if (dp[i][j][N] > 0) return dp[i][j][N];

        dp[i][j][N] = (dp[i][j][N] + helper(m, n, N - 1, i + 1, j, dp)) % 1000000007;
        dp[i][j][N] = (dp[i][j][N] + helper(m, n, N - 1, i, j + 1, dp)) % 1000000007;
        dp[i][j][N] = (dp[i][j][N] + helper(m, n, N - 1, i - 1, j, dp)) % 1000000007;
        dp[i][j][N] = (dp[i][j][N] + helper(m, n, N - 1, i, j - 1, dp)) % 1000000007;

        return dp[i][j][N];
    }