34 ms JAVA solution, dp, with restrictions on maximum steps for each cell


  • 0
    J

    Pretty straightforward

        public int findPaths(int m, int n, int N, int i, int j) {
        	if (N==0) return 0;
            int[][][] dp = new int[m][n][N];
            dp[i][j][0] = 1;
            int[][] maxstep = new int[m][n];
            for (int i1=0;i1<m;i1++)
                for (int j1=0;j1<n;j1++)
                    maxstep[i1][j1] = N-(Math.min(Math.min(Math.min(i1+1,j1+1),m-i1),n-j1));
            for (int k=0;k<N;k++){
            	for (int i1=0;i1<m;i1++){
            		for(int j1=0;j1<n;j1++){
                        if (i1>0 && maxstep[i1-1][j1]>k){
                            dp[i1-1][j1][k+1] += dp[i1][j1][k];
                            dp[i1-1][j1][k+1]%=(1000000000 + 7);
                        }
                        if (j1>0 && maxstep[i1][j1-1]>k){
                            dp[i1][j1-1][k+1] += dp[i1][j1][k];
                            dp[i1][j1-1][k+1]%=(1000000000 + 7);
                        }
                        if (i1<m-1 && maxstep[i1+1][j1]>k){
                            dp[i1+1][j1][k+1] += dp[i1][j1][k];
                            dp[i1+1][j1][k+1]%=(1000000000 + 7);
                        }
                        if (j1<n-1 && maxstep[i1][j1+1]>k){
                            dp[i1][j1+1][k+1] += dp[i1][j1][k];
                            dp[i1][j1+1][k+1]%=(1000000000 + 7);
                        }
            		}
            	}
            }
            int res = 0;
            for (int i1=0;i1<m;i1++){
                for (int k=0;k<N;k++){
                    res+=(long)(dp[i1][0][k]+dp[i1][n-1][k])%(1000000000 + 7);
                    res%=(1000000000 + 7);
                }
            }
            for (int j1=0;j1<n;j1++){
                for (int k=0;k<N;k++){
                    res+=(long)(dp[0][j1][k]+dp[m-1][j1][k])%(1000000000 + 7);
                    res%=(1000000000 + 7);
                }
            }
            return res%(1000000000 + 7);
        }
    

Log in to reply
 

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