Java Solution


  • 0
    Z

    '''
    public class Solution {

    private static Integer[][][] deep;
    
    public int findPaths(int m, int n, int N, int i, int j) {
        
        deep= new Integer[m][n][N+1];
        int[][] matrix1=this.matrixNear( m,  n,  i, j);
        
        int result=0;
        //4 Cases
        int w,t;
        boolean move =false;
        w=0;
        for(t=0;t<n;t++){
            if(w==i&&t==j) move=true;
            result=(result+nPath(matrix1, w,  t,  i,  j, N-1, move)) % 1000000007;  
        }
        move =false;
        w=m-1;
        for(t=0;t<n;t++){
            if(w==i&&t==j) move=true;
            result=(result+nPath(matrix1, w,  t,  i,  j, N-1, move)) % 1000000007; 
        }
        move =false;
        t=0;
        for(w=0;w<m;w++){
            if(w==i&&t==j) move=true;
            result=(result+nPath(matrix1, w,  t,  i,  j, N-1, move)) % 1000000007; 
        }
        move =false;
        t=n-1;
        for(w=0;w<m;w++){
            if(w==i&&t==j) move=true;
            result=(result+nPath(matrix1, w,  t,  i,  j, N-1, move)) % 1000000007;    
        }
        return result % 1000000007;
    }
    
    
    //Get the matrix with nearest way to i j
    private int nearestWay(int x1, int y1, int x2, int y2){
        return Math.abs(x1-x2)+Math.abs(y1-y2);
    }
    
    private int[][] matrixNear(int m, int n, int x1, int y1){
        int[][] result=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                result[i][j]=nearestWay(i,j,x1,y1);
            }
        }
        return result;
    }
        
    //From one case to another caculate the number of possible path
    private int nPath(int[][] matrix, int x1, int y1, int x2, int y2, int step, boolean move){
        if(step<0) return 0;
        if(deep[x1][y1][step]!=null){
          return (int)deep[x1][y1][step];  
        } 
        int result=0;
        int length=matrix.length;
        int width=matrix[0].length;
        
        if(x1==x2&&y1==y2){ 
            if(step>=0) result++;
            if(step==0)  return result;
        }
        
        for(int i=x1-1;i<=x1+1;i++){
            for(int j=y1-1;j<=y1+1;j++){
                if(!(i==x1+1&&j==y1+1)&&!(i==x1-1&&j==y1-1)&&!(i==x1+1&&j==y1-1)&&!(i==x1-1&&j==y1+1)){
                if((!(i==x1&&j==y1))&&i>=0&&j>=0&&i<length&&j<width){
                    if(matrix[i][j]<=(step-1)){
                      result=(result+nPath(matrix, i, j, x2, y2, step-1,move))% 1000000007;  
                    } 
                }
            }
                
            }
        }
        result=result % 1000000007;
        deep[x1][y1][step]=(Integer)result;
        return result;
    }
    

    }
    '''


Log in to reply
 

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