# O(Nmn) time, O(mn) space solution

• C++

``````class Solution {
public:
int findPaths(int m, int n, int N, int i, int j) {
vector<vector<vector<int>>> dp(2, vector<vector<int>>(m, vector<int>(n, 0)));
int M = 1000000007, curr = 0, next = 1;
for (int k = 0; k < N; ++k, swap(curr, next)) {
for (int x = 0; x < m; ++x) {
for (int y = 0; y < n; ++y) {
dp[next][x][y] = (((!x ? 1 : dp[curr][x - 1][y]) + (x + 1 == m ? 1 : dp[curr][x + 1][y])) % M
+ ((!y ? 1 : dp[curr][x][y - 1]) + (y + 1 == n ? 1 : dp[curr][x][y + 1])) % M) % M;
}
}
}
return dp[curr][i][j];
}
};
``````

Java

``````public class Solution {
public int findPaths(int m, int n, int N, int i, int j) {
int[][][] dp = new int[2][m][n];
int curr = 0, next = 1, M = 1000000007;
for (int k = 0; k < N; k++) {
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
dp[next][x][y] = (((x == 0 ? 1 : dp[curr][x - 1][y]) + (x + 1 == m ? 1 : dp[curr][x + 1][y])) % M
+ ((y == 0 ? 1 : dp[curr][x][y - 1]) + (y + 1 == n ? 1 : dp[curr][x][y + 1])) % M) % M;
}
}
int t = curr;
curr = next;
next = t;
}
return dp[curr][i][j];
}
}
``````

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