# Java clear solution, iteration

• ``````public class Solution {
public int findPaths(int m, int n, int N, int i, int j) {
if(N<=0) return 0;
//get level 1.
int[][] matrix = new int[m][n];
for(int a=0;a<m;a++){
for(int b=0;b<n;b++){
if(a==0) matrix[a][b]++;
if(b==0) matrix[a][b]++;
if(a+1==m) matrix[a][b]++;
if(b+1==n) matrix[a][b]++;
}
}
//iterate to N.
//F(n)(i,j) = sum(F(n-1) by four neighbor of (i,j))
//f(i,j,N) = f(i-1,j,N-1)+f(i+1,j,N-1)+f(i,j-1,N-1)+f(i,j+1,N-1)
int res = matrix[i][j];
for(int k=1;k<N;k++){
int[][] next = new int[m][n];
for(int a=0;a<m;a++){
for(int b=0;b<n;b++){
if(a>0) next[a][b] = (next[a][b] + matrix[a-1][b])%1000000007;
if(b>0) next[a][b] = (next[a][b] + matrix[a][b-1])%1000000007;
if(a+1<m) next[a][b] = (next[a][b] + matrix[a+1][b])%1000000007;
if(b+1<n) next[a][b] = (next[a][b] + matrix[a][b+1])%1000000007;
}
}
matrix = next;
res = (res + matrix[i][j])%1000000007;
}
return res;
}
}
``````

• Genius! How did you come up with this idea?

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