DP, C++


  • 0
    I
    class Solution {
    public:
        int get(vector<vector<vector<int>>> &dp, int k, int i, int j)
        {
            if(i < 0 || j < 0 || i >= dp[0].size() || j >= dp[0][0].size())
               return 1;
            return dp[k][i][j];
              
        }
        int findPaths(int m, int n, int N, int i, int j) {
            if(!N || i < 0 || j < 0 || i >= m || j >= n) return 0;
            vector<vector<vector<int>>> dp(N,vector<vector<int>>(m,vector<int>(n,0)));
            for(int i = 0; i < m; ++i)
            {
               ++dp[0][i][0];
               ++dp[0][i][n-1];
            }
            for(int j = 0; j < n; ++j)
            {
               ++dp[0][0][j];
               ++dp[0][m-1][j];
            }
            int mod = 1000000007;
            for(int k = 1; k < N; ++k)
            {
                for(int i = 0; i < m; ++i)
                for(int j = 0; j < n; ++j)
                {
                    dp[k][i][j] += get(dp,k-1,i-1,j);
                    dp[k][i][j] %= mod;
                    dp[k][i][j] += get(dp,k-1,i+1,j);
                    dp[k][i][j] %= mod;
                    dp[k][i][j] += get(dp,k-1,i,j-1);
                    dp[k][i][j] %= mod;
                    dp[k][i][j] += get(dp,k-1,i,j+1);
                    dp[k][i][j] %= mod;
                    
                }
            }
            return dp[N-1][i][j];
        }
    };

Log in to reply
 

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