# Simple O(n*M*N) solution

• """
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.

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