# Java Solution

• '''
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;
}
``````

}
'''

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