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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
 * Find the number of paths to move the ball out of the grid boundary.
 * Dynamic Programming (3D) approach with recursion and memoization.
 *
 * @param {number} m - Number of rows in the grid
 * @param {number} n - Number of columns in the grid
 * @param {number} maxMove - Maximum number of moves allowed
 * @param {number} startRow - Starting row position
 * @param {number} startColumn - Starting column position
 * @return {number} - Number of paths to move the ball out of the grid boundary
 */
function findPaths(m, n, maxMove, startRow, startColumn) {
  // Define the modulo value
  const MOD = 1000000007;
 
  // Initialize the DP array
  const dp = Array(m).fill().map(() =>
    Array(n).fill().map(() =>
      Array(maxMove + 1).fill(-1)
    )
  );
 
  /**
   * Recursive function to find the number of paths.
   *
   * @param {number} i - Current row position
   * @param {number} j - Current column position
   * @param {number} k - Number of moves remaining
   * @return {number} - Number of paths to move the ball out of the grid boundary
   */
  function dfs(i, j, k) {
    // Base case: If the ball is out of the grid boundary, return 1
    if (i < 0 || i >= m || j < 0 || j >= n) {
      return 1;
    }
 
    // Base case: If there are no moves remaining, return 0
    if (k === 0) {
      return 0;
    }
 
    // If the subproblem has already been solved, return the result
    if (dp[i][j][k] !== -1) {
      return dp[i][j][k];
    }
 
    // Initialize the result
    let result = 0;
 
    // Consider all four directions
    result = (result + dfs(i - 1, j, k - 1)) % MOD;  // Up
    result = (result + dfs(i + 1, j, k - 1)) % MOD;  // Down
    result = (result + dfs(i, j - 1, k - 1)) % MOD;  // Left
    result = (result + dfs(i, j + 1, k - 1)) % MOD;  // Right
 
    // Store the result in the DP array
    dp[i][j][k] = result;
 
    return result;
  }
 
  // Call the recursive function with the initial position and maximum moves
  return dfs(startRow, startColumn, maxMove);
}
 
/**
 * Find the number of paths to move the ball out of the grid boundary.
 * Dynamic Programming (Iterative) approach.
 *
 * @param {number} m - Number of rows in the grid
 * @param {number} n - Number of columns in the grid
 * @param {number} maxMove - Maximum number of moves allowed
 * @param {number} startRow - Starting row position
 * @param {number} startColumn - Starting column position
 * @return {number} - Number of paths to move the ball out of the grid boundary
 */
function findPathsIterative(m, n, maxMove, startRow, startColumn) {
  // Define the modulo value
  const MOD = 1000000007;
 
  // Initialize the DP array
  const dp = Array(maxMove + 1).fill().map(() =>
    Array(m).fill().map(() =>
      Array(n).fill(0)
    )
  );
 
  // Initialize the starting position
  dp[0][startRow][startColumn] = 1;
 
  // Initialize the result
  let result = 0;
 
  // Define the four directions: up, down, left, right
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
 
  // Iterate through all moves
  for (let k = 1; k <= maxMove; k++) {
    // Iterate through all positions in the grid
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        // Skip if there are no ways to reach this position with k-1 moves
        if (dp[k - 1][i][j] === 0) {
          continue;
        }
 
        // Consider all four directions
        for (const [di, dj] of directions) {
          const ni = i + di;
          const nj = j + dj;
 
          // If the new position is out of the grid boundary, add to the result
          if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
            result = (result + dp[k - 1][i][j]) % MOD;
          } else {
            // Otherwise, add to the DP array
            dp[k][ni][nj] = (dp[k][ni][nj] + dp[k - 1][i][j]) % MOD;
          }
        }
      }
    }
  }
 
  return result;
}
 
// Test cases
console.log(findPaths(2, 2, 2, 0, 0));  // 6
console.log(findPaths(1, 3, 3, 0, 1));  // 12
 
console.log(findPathsIterative(2, 2, 2, 0, 0));  // 6
console.log(findPathsIterative(1, 3, 3, 0, 1));  // 12