Easy understand c++ 9ms using 2*m*n space with explaination


  • 0
    J

    table[i][j] is the path number of rolling k steps for cell (i,j). next[i][j] is the path number of rolling k+1 steps for cell(i,j). hence next[i][j]=table[i-1][j]+table[i][j-1]+table[i+1][j]+table[i][j+1]. If only roll 1 steps, only boundary cell has value. initialize it at beginning.

    class Solution {
    public:
        int findPaths(int m, int n, int N, int i, int j) {
            vector<vector<size_t>> table(m, vector<size_t>(n, 0));
            
            size_t ans=0;
            
            for(int k=1; k<=N; k++)
            {
                vector<vector<size_t>> next(m, vector<size_t>(n, 0));
                if(k==1)
                {
                    for(int x=0; x<m; x++)
                    {
                        for(int y=0; y<n; y++)
                        {
                            if(x==0)
                                ++table[x][y];
                            if(y==0)
                                ++table[x][y];
                            if(y==n-1)
                                ++table[x][y];
                            if(x==m-1)
                                ++table[x][y];
                          
                        }
                    }
                }
                else
                {
                    for(int x=0; x<m; x++)
                    {
                        for(int y=0; y<n; y++)
                        {
                           size_t val=0;
                          
                           val+=(x==0?0:table[x-1][y]);
                           
                           val+=(y==0?0:table[x][y-1]);
                           
                           val+=(x==m-1?0:table[x+1][y]);
                           
                           val+=(y==n-1?0:table[x][y+1]);
                           next[x][y]=val%mod;                      
                        }
                    }
                    table=next;
                }
                ans=(ans+table[i][j])%mod;
            }
            return ans;
        }
        
    private:
        const int mod=1e9+7;
    };
    

Log in to reply
 

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