• Time:O(mnN)
• Space:O(mnN)

## C++

``````class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
this->m = m;
this->n = n;
// dp[k][i][j] := # of paths to move the ball (i, j) out of bound w/ k moves
dp.resize(maxMove + 1, vector<vector<int>>(m, vector<int>(n, -1)));
return findPaths(maxMove, startRow, startColumn);
}

private:
constexpr static int kMod = 1e9 + 7;
int m;
int n;
vector<vector<vector<int>>> dp;

int findPaths(int k, int i, int j) {
if (i < 0 || i == m || j < 0 || j == n)
return 1;
if (k == 0)
return 0;
if (dp[k][i][j] != -1)
return dp[k][i][j];
return dp[k][i][j] =
((findPaths(k - 1, i + 1, j) + findPaths(k - 1, i - 1, j)) % kMod +
(findPaths(k - 1, i, j + 1) + findPaths(k - 1, i, j - 1)) % kMod) %
kMod;
}
};
``````

## JAVA

``````class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
this.m = m;
this.n = n;
// dp[k][i][j] := # of paths to move the ball (i, j) out of bound w/ k moves
dp = new Integer[maxMove + 1][m][n];
return findPaths(maxMove, startRow, startColumn);
}

private static final int kMod = (int) 1e9 + 7;
private int m;
private int n;
private Integer[][][] dp;

private int findPaths(int k, int i, int j) {
if (i < 0 || i == m || j < 0 || j == n)
return 1;
if (k == 0)
return 0;
if (dp[k][i][j] != null)
return dp[k][i][j];
return dp[k][i][j] = ((findPaths(k - 1, i + 1, j) + findPaths(k - 1, i - 1, j)) % kMod +
(findPaths(k - 1, i, j + 1) + findPaths(k - 1, i, j - 1)) % kMod) %
kMod;
}
}
``````

• Time:O(mnN)
• Space:O(mn)

## C++

``````class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
constexpr int kMod = 1e9 + 7;
const vector<int> dirs{0, 1, 0, -1, 0};
int ans = 0;
// dp[i][j] := # of paths to move the ball (i, j) out of bound
vector<vector<int>> dp(m, vector<int>(n));
dp[startRow][startColumn] = 1;

while (maxMove--) {
vector<vector<int>> newDp(m, vector<int>(n));
for (int r = 0; r < m; ++r)
for (int c = 0; c < n; ++c)
if (dp[r][c] > 0)
for (int k = 0; k < 4; ++k) {
const int x = r + dirs[k];
const int y = c + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
ans = (ans + dp[r][c]) % kMod;
else
newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod;
}
dp = move(newDp);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
final int kMod = (int) 1e9 + 7;
final int[] dirs = {0, 1, 0, -1, 0};
int ans = 0;
// dp[i][j] := # of paths to move the ball (i, j) out of bound
int[][] dp = new int[m][n];
dp[startRow][startColumn] = 1;

while (maxMove-- > 0) {
int[][] newDp = new int[m][n];
for (int r = 0; r < m; ++r)
for (int c = 0; c < n; ++c)
if (dp[r][c] > 0)
for (int k = 0; k < 4; ++k) {
final int x = r + dirs[k];
final int y = c + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
ans = (ans + dp[r][c]) % kMod;
else
newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod;
}
dp = newDp;
}

return ans;
}
}
``````

## Python

``````class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
kMod = int(1e9) + 7
dirs = [1, 0, -1, 0, 1]
ans = 0
# dp[i][j] := # of paths to move the ball (i, j) out of bound
dp = [[0] * n for _ in range(m)]
dp[startRow][startColumn] = 1

for _ in range(maxMove):
newDp = [[0] * n for _ in range(m)]
for r in range(m):
for c in range(n):
if dp[r][c] > 0:
for dx, dy in zip(dirs, dirs[1:]):
x = r + dx
y = c + dy
if x < 0 or x == m or y < 0 or y == n:
ans = (ans + dp[r][c]) % kMod
else:
newDp[x][y] = (newDp[x][y] + dp[r][c]) % kMod
dp = newDp

return ans
``````