# Java Solution

• public class Solution {

``````private static int[][][] deep;

public int findPaths(int m, int n, int N, int i, int j) {

if(N==0) return 0;

deep= new int[m][n][3];
deep[i][j][0]=1;
deep[i][j][1]=1;
int result=0;

for(int z=0;z<N-1;z++){
fillM(m,n);

}

//4 Cases
int w,t;
w=0;
for(t=0;t<n;t++){
result=(result+deep[w][t][0]) % 1000000007;
}
w=m-1;
for(t=0;t<n;t++){
result=(result+deep[w][t][0]) % 1000000007;
}
t=0;
for(w=0;w<m;w++){
result=(result+deep[w][t][0]) % 1000000007;
}
t=n-1;
for(w=0;w<m;w++){
result=(result+deep[w][t][0]) % 1000000007;
}
return result % 1000000007;
}

//Get the matrix with nearest way to i j
private void fillM(int m, int n){
//Update from step n-1
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
for(int x=i-1;x<=i+1;x++){
for(int y=j-1;y<=j+1;y++){
if(!(x==i+1&&y==j+1)&&!(x==i-1&&y==j-1)&&!(x==i+1&&y==j-1)&&!(x==i-1&&y==j+1)){
if((!(x==i&&y==j))&&x>=0&&y>=0&&x<m&&y<n){
deep[i][j][2]=(deep[i][j][2]+deep[x][y][1])% 1000000007;
}
}
}
}
}
}

//Copy from matrix1 and reset matrix1 to 0
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
deep[i][j][0]=(deep[i][j][0]+deep[i][j][2])% 1000000007;
deep[i][j][1]=deep[i][j][2];
deep[i][j][2]=0;
}
}

}
``````

}

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