Simple O(n*M*N) solution


  • 0
    P

    """
    public class Solution {
    private int sum=0;
    int [][]dirs={{1,0},{0,1},{-1,0},{0,-1}};

    public int findPaths(int m, int n, int N, int i, int j) {
        long [][][]dp=new long[m][n][N+1];
        int k = 1;
        
        if (N == 0)
            return (0);
    
        for(int p=0;p<m;p++) {
             for(int q=0;q<n;q++) {
                 dp[p][q][k] = 0;
                 if (p == 0) dp[p][q][k] += 1; if (q == 0) d[p][q][k] += 1; if (p == m - 1) dp[p][q][k] += 1; if (q == n - 1) dp[p][q][k] += 1;
             }
        }
        
        sum += dp[i][j][k]; 
    
        for(k = 2;k <= N;k++) {
            for(int p = 0;p < m;p++) {
                for(int q = 0;q < n; q++)
                {
                    for(int []d : dirs){
                        int x = p + d[0], y = q + d[1];
                        if(x >= 0 && y >= 0 && x <= m-1 && y <= n-1)
                            dp[p][q][k] += (dp[x][y][k - 1]%(1000000007)+   (1000000007))%(1000000007);
                    }
                }
    
            }
                sum += ((long)dp[i][j][k]%(1000000007));
                sum=sum%(1000000007);
        }
            return (int)sum;
    }
    

    }
    """

    The idea is to check if it is possible to go beyond the boundary in k steps from a particular point.


Log in to reply
 

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