Problem
There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.
Example 1:
Input:m = 2, n = 2, N = 2, i = 0, j = 0 Output: 6 Explanation:
Example 2:
Input:m = 1, n = 3, N = 3, i = 0, j = 1 Output: 12 Explanation:
Note:
- Once you move the ball out of boundary, you cannot move it back.
- The length and height of the grid is in range [1,50].
- N is in range [0,50].
Solution
Time complexity: O(m*n + N * m * n)
Space complexity: O(N*m*n) -> O(m*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 19 ms class Solution { public: int findPaths(int m, int n, int N, int i, int j) { constexpr int kMod = 1000000007; vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0))); vector<int> dirs{-1, 0, 1, 0, -1}; for (int s = 1; s <= N; ++s) for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) for (int d = 0; d < 4; ++d) { int tx = x + dirs[d]; int ty = y + dirs[d + 1]; if (tx < 0 || ty < 0 || tx >= n || ty >= m) dp[s][y][x] += 1; else dp[s][y][x] = (dp[s][y][x] + dp[s - 1][ty][tx]) % kMod; } return dp[N][i][j]; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua // Running time: 16 ms class Solution { public: int findPaths(int m, int n, int N, int i, int j) { constexpr int kMod = 1000000007; vector<vector<int>> dp(m, vector<int>(n, 0)); vector<int> dirs{-1, 0, 1, 0, -1}; for (int s = 1; s <= N; ++s) { vector<vector<int>> tmp(m, vector<int>(n, 0)); for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) for (int d = 0; d < 4; ++d) { int tx = x + dirs[d]; int ty = y + dirs[d + 1]; if (tx < 0 || ty < 0 || tx >= n || ty >= m) tmp[y][x] += 1; else tmp[y][x] = (tmp[y][x] + dp[ty][tx]) % kMod; } dp.swap(tmp); } return dp[i][j]; } }; |
Recursion with memorization
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Author: Huahua // Running time: 4 ms class Solution { public: int findPaths(int m, int n, int N, int i, int j) { m_ = m; n_ = n; dp_ = vector<vector<vector<int>>>(N + 1, vector<vector<int>>(m, vector<int>(n, INT_MIN))); return paths(N, j, i); } private: vector<vector<vector<int>>> dp_; int m_; int n_; // number of paths starts from out-of-boundary to (x, y) by moving at most N steps. int paths(int N, int x, int y) { static vector<int> dirs{-1, 0, 1, 0, -1}; static const int kMod = 1000000007; // Out of boundary, one path. if (x < 0 || x >= n_ || y < 0 || y >= m_) return 1; // Can not move but still in the grid, no path. if (N == 0) return 0; // Already computed. if (dp_[N][y][x] != INT_MIN) return dp_[N][y][x]; dp_[N][y][x] = 0; for (int d = 0; d < 4; ++d) { int tx = x + dirs[d]; int ty = y + dirs[d + 1]; dp_[N][y][x] = (dp_[N][y][x] + paths(N - 1, tx, ty)) % kMod; } return dp_[N][y][x]; } }; |
no loops
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua // Running time: 4 ms class Solution { public: int findPaths(int m, int n, int N, int i, int j) { m_ = m; n_ = n; dp_ = vector<vector<vector<int>>>(N + 1, vector<vector<int>>(m, vector<int>(n, INT_MIN))); return paths(N, j, i); } private: vector<vector<vector<int>>> dp_; int m_; int n_; // number of paths start from (x, y) and move at most N steps. int paths(int N, int x, int y) { static const int kMod = 1000000007; if (x < 0 || x >= n_ || y < 0 || y >= m_) return 1; if (N == 0) return 0; if (dp_[N][y][x] != INT_MIN) return dp_[N][y][x]; long ans = 0; ans += paths(N - 1, x + 1, y); ans += paths(N - 1, x - 1, y); ans += paths(N - 1, x, y + 1); ans += paths(N - 1, x, y - 1); ans %= kMod; return dp_[N][y][x] = ans; } }; |