Sponsored
Sponsored
The main idea is to use a 3D dynamic programming array dp[i][j][k] where i and j represent the current position on the grid, and k represents the number of moves remaining. The value at dp[i][j][k] represents the number of ways to move the ball out of bounds using at most k moves starting from (i, j).
Transitions are made by moving the ball in one of the four possible directions and decreasing the move count. If the ball goes out of bounds, increment the path count. The answer is the sum of paths from startRow, startColumn using maxMove moves.
Time Complexity: O(m * n * maxMove) as each grid cell and move combination is processed exactly once.
Space Complexity: O(m * n * maxMove) due to the storage of the DP array.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
7 vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(maxMove + 1)));
8 int MOD = 1000000007;
9 vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10 dp[startRow][startColumn][0] = 1;
11 int count = 0;
12 for (int move = 1; move <= maxMove; move++) {
13 for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (auto& d : directions) {
int ni = i + d[0];
int nj = j + d[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i][j][move-1]) % MOD;
} else {
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move-1]) % MOD;
}
}
}
}
}
return count;
}
};This C++ solution mirrors the dynamic programming approach, using vectors to store paths results. For each possible move, it adjusts position coordinates, checks boundaries, and updates the path count, with results ultimately returning the number of successful paths out of the boundary.
DFS with memoization is used to prevent recalculating results for already evaluated states by storing them in a map or dictionary. Each call is a recursive attempt to move in all directions from the current cell, decrementing the move count. Result of out-of-bounds attempts is stored so it can be reused, avoiding exponential time complexity.
This algorithm uses a function that considers the current position and remaining moves. For every call, explore in four possible directions and add to the path count if the ball gets out of bounds. Store already calculated counts in a dictionary for path optimization.
Time Complexity: O(m * n * maxMove) where each state is visited only once.
Space Complexity: O(m * n * maxMove) due to memoization storage.
public class Solution {
private const int MOD = 1000000007;
private int[,,] memo;
public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
memo = new int[m, n, maxMove + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k <= maxMove; k++)
memo[i, j, k] = -1;
return Dfs(m, n, maxMove, startRow, startColumn);
}
private int Dfs(int m, int n, int move, int row, int col) {
if (row < 0 || row >= m || col < 0 || col >= n) return 1;
if (move == 0) return 0;
if (memo[row, col, move] != -1) return memo[row, col, move];
int result = 0;
int[][] directions = new [] { new []{1, 0}, new []{-1, 0}, new []{0, 1}, new []{0, -1} };
foreach (var dir in directions) {
result = (result + Dfs(m, n, move - 1, row + dir[0], col + dir[1])) % MOD;
}
memo[row, col, move] = result;
return result;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindPaths(2, 2, 2, 0, 0)); // Output: 6
Console.WriteLine(solution.FindPaths(1, 3, 3, 0, 1)); // Output: 12
}
}This C# solution utilizes DFS and memoization, enabling effective reuse of computed values to decrease operations on recurring operations. The count accumulates the routes where boundary escapes are plausible through detailed directional shifts.