There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.
Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 Output: 6
Example 2:
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 Output: 12
Constraints:
1 <= m, n <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n
Companies:
Amazon
Related Topics:
Dynamic Programming
Similar Questions:
Let dp[x][y][k] be the number of out-of-boundary moves starting from cell (x, y) with at most k moves.
dp[x][y][k] = SUM( dp[a][b][k - 1] | (a,b) is a neighbor of (x, y) )
dp[x][y][k] = 1 if (x, y) is out-of-boundary, and 0 <= k <= maxMoves
dp[x][y][0] = 0 if (x, y) is not out-of-boundary
The answer is dp[startRow][startColumn][maxMove].
// OJ: https://leetcode.com/problems/out-of-boundary-paths/
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(MNK)
class Solution {
long m, n, dp[50][50][51] = {}, dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, mod = 1e9 + 7;
int dfs(int x, int y, int k) {
if (x < 0 || x >= m || y < 0 || y >= n) return 1;
if (k == 0) return 0;
if (dp[x][y][k] != -1) return dp[x][y][k];
long cnt = 0;
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
cnt = (dfs(a, b, k - 1) + cnt) % mod;
}
return dp[x][y][k] = cnt;
}
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
this->m = m;
this->n = n;
memset(dp, -1, sizeof(dp));
return dfs(startRow, startColumn, maxMove);
}
};Let dp[x][y][k] be the number of out-of-boundary moves starting from cell (x, y) with exactly k moves.
dp[x][y][k] = SUM( dp[a][b][k - 1] | (a,b) is a neighor of (x,y) )
dp[x][y][0] = 1 if (x,y) is out-of-boundary
dp[x][y][0] = 0 if (x,y) is not out-of-boundary
dp[x][y][k] = 0 if (x,y) is out-of-boundary and k > 0
// OJ: https://leetcode.com/problems/out-of-boundary-paths/
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(MNK)
class Solution {
long m, n, dp[50][50][51] = {}, dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, mod = 1e9 + 7;
int dfs(int x, int y, int step) {
int oob = x < 0 || x >= m || y < 0 || y >= n;
if (step == 0) return oob;
if (oob) return 0;
if (dp[x][y][step] != -1) return dp[x][y][step];
long cnt = 0;
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
cnt = (dfs(a, b, step - 1) + cnt) % mod;
}
return dp[x][y][step] = cnt;
}
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
this->m = m;
this->n = n;
long ans = 0;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= maxMove; ++i) ans = (ans + dfs(startRow, startColumn, i)) % mod;
return ans;
}
};Or
// OJ: https://leetcode.com/problems/out-of-boundary-paths/
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(MNK)
class Solution {
long m, n, dp[50][50][51] = {}, dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}, mod = 1e9 + 7;
int dfs(int x, int y, int k) {
if (dp[x][y][k] != -1) return dp[x][y][k];
if (k == 1) {
int cnt = 0;
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
cnt += a < 0 || a >= m || b < 0 || b >= n;
}
return dp[x][y][k] = cnt;
}
long cnt = 0;
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
if (a < 0 || a >= m || b < 0 || b >= n) continue;
cnt = (dfs(a, b, k - 1) + cnt) % mod;
}
return dp[x][y][k] = cnt;
}
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
this->m = m;
this->n = n;
long ans = 0;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= maxMove; ++i) ans = (ans + dfs(startRow, startColumn, i)) % mod;
return ans;
}
};Let dp[i][j][k] be the number of ways to go out of boundary from point (i, j) using exactly k steps.
dp[i][j][k] = SUM( dp[a][b][k - 1] | (a, b) is neighbor of (i, j) )
dp[i][j][1] is the number of edges the point (i, j) touches.
The answer is SUM( dp[x][y][k] | k = 1, 2, ..., maxMoves ).
Why not define dp[i][j][k] as the number of ways to go out of boundary from point (i, j) with at most k steps?
Because when computing dp[i][j][k], assume we know dp[i][j][k - 1], then we need to compute the ways to go out of boundary with exact k steps. So we need the number of ways with exact k steps any way.
// OJ: https://leetcode.com/problems/out-of-boundary-paths/
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(MN)
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
if (maxMove == 0) return 0;
int dp[50][50][2] = {}, dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, mod = 1e9 + 7;
for (int i = 0; i < m; ++i) dp[i][0][1]++, dp[i][n - 1][1]++;
for (int i = 0; i < n; ++i) dp[0][i][1]++, dp[m - 1][i][1]++;
int ans = dp[startRow][startColumn][1];
for (int k = 2; k <= maxMove; ++k) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int val = 0;
for (auto &[dx, dy] : dirs) {
int a = i + dx, b = j + dy;
if (a < 0 || a >= m || b < 0 || b >= n) continue;
val = (val + dp[a][b][(k - 1) % 2]) % mod;
}
dp[i][j][k % 2] = val;
}
}
ans = (ans + dp[startRow][startColumn][k % 2]) % mod;
}
return ans;
}
};Let dp[i][j][k] be the number of ways to go from starting point (x, y) to point (i, j) with exactly k steps.
So dp[x][y][0] = 1.
dp[i][j][k] = SUM( dp[a][b][k - 1] | (a, b) is neighbor of (i, j) )
dp[i][j][k] should be added into answer if point (i, j) is at the boundary (i.e. i == 0 || i == M - 1 || j == 0 || j == N - 1) and 0 <= k < maxMoves.
// OJ: https://leetcode.com/problems/out-of-boundary-paths/
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(MN)
// Ref: https://leetcode.com/problems/out-of-boundary-paths/solution/
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
if (maxMove == 0) return 0;
long dp[50][50][2] = {}, dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, mod = 1e9 + 7, ans = 0;
dp[startRow][startColumn][0] = 1;
for (int k = 0; k < maxMove; ++k) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int val = dp[i][j][k % 2], cnt = (i == 0) + (i == m - 1) + (j == 0) + (j == n - 1);
ans = (ans + cnt * val % mod) % mod;
val = 0;
for (auto &[dx, dy] : dirs) {
int a = i + dx, b = j + dy;
if (a < 0 || a >= m || b < 0 || b >= n) continue;
val = (val + dp[a][b][k % 2]) % mod;
}
dp[i][j][(k + 1) % 2] = val;
}
}
}
return ans;
}
};