O(Nmn) time, O(mn) space solution


  • 0
    A

    C++

    class Solution {
    public:
        int findPaths(int m, int n, int N, int i, int j) {
            vector<vector<vector<int>>> dp(2, vector<vector<int>>(m, vector<int>(n, 0)));
            int M = 1000000007, curr = 0, next = 1;
            for (int k = 0; k < N; ++k, swap(curr, next)) {
                for (int x = 0; x < m; ++x) {
                    for (int y = 0; y < n; ++y) {
                        dp[next][x][y] = (((!x ? 1 : dp[curr][x - 1][y]) + (x + 1 == m ? 1 : dp[curr][x + 1][y])) % M
                                    + ((!y ? 1 : dp[curr][x][y - 1]) + (y + 1 == n ? 1 : dp[curr][x][y + 1])) % M) % M;
                    }
                }
            }
            return dp[curr][i][j];
        }
    };
    

    Java

    public class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            int[][][] dp = new int[2][m][n];
            int curr = 0, next = 1, M = 1000000007;
            for (int k = 0; k < N; k++) {
                for (int x = 0; x < m; x++) {
                    for (int y = 0; y < n; y++) {
                        dp[next][x][y] = (((x == 0 ? 1 : dp[curr][x - 1][y]) + (x + 1 == m ? 1 : dp[curr][x + 1][y])) % M
                                        + ((y == 0 ? 1 : dp[curr][x][y - 1]) + (y + 1 == n ? 1 : dp[curr][x][y + 1])) % M) % M;
                    }
                }
                int t = curr;
                curr = next;
                next = t;
            }
            return dp[curr][i][j];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.