Easy-understanding C++ & Python solution with explanation


  • 2

    The time complexity of answer is O(mnN).

    And we need to use dynamic programming (for remembering the existing searching) and DFS (for searching the answer) to solve this problem.

    C++ version:

    class Solution {
    private:
        int m, n, N, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
        const int mod = 1e9 + 7;
        bool check(int i, int j) {return i >= m || j >= n || i < 0 || j < 0;}
    public:
        int findPaths(int m, int n, int N, int i, int j) {
            this->m = m, this->n = n, this->N = N;
            vector<vector<int>> dp(m * n, vector<int>(N, -1));
            return solve(i, j, N, dp, 0);
        }
        int solve(int i, int j, int step, vector<vector<int>>& dp, int ans) {
            if (check(i, j)) return 1; // out of boundary, count as 1 way
            if (step == 0) return 0; // without steps but not out of bounday, don't count as a way
            if (dp[i*n + j][step-1] == -1) {
                // the answer came from 4 paths: top, down, left, right
                for (int k=0; k<4; ++k) 
                    ans = (ans + solve(i + dx[k], j + dy[k], step-1, dp, 0) % mod) % mod;
                dp[i*n + j][step-1] = ans;
            }
            return dp[i*n + j][step-1];
        }
    };
    

    Python version:

    class Solution(object):
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        lc = 1e9 + 7
    
        def solve(self, i, j, step, dp, ans, m, n, N):
            if i >= m or j >= n or i < 0 or j < 0:
                return 1
            if step == 0:
                return 0
            if dp[i*n +j][step - 1] == -1:
                for k in xrange(4):
                    ans = (ans + self.solve(i + self.dx[k], j + self.dy[k], step-1, dp, 0, m, n, N) % self.lc) % self.lc
                dp[i*n + j][step - 1] = ans
            return int(dp[i*n + j][step - 1])
            
        def findPaths(self, m, n, N, i, j):
            dp = [[-1 for t in xrange(N)] for k in xrange(m*n)]
            return self.solve(i, j, N, dp, 0, m, n, N)
    

  • 0
    E
    This post is deleted!

Log in to reply
 

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