Out of Boundary Paths

Updated on 04 July, 2025
Out of Boundary Paths header image

Problem Statement

In a given problem, we are working with an m x n grid where a ball is placed initially at a specified location [startRow, startColumn]. The core task is to compute how many distinct paths are available for this ball to exit the grid, given that it can only make a limited number of moves, precisely maxMove moves. A move is defined as shifting the ball to any of its four adjacent grid cells (Up, Down, Left, Right). It should be noted that moving the ball out of the grid's boundary is regarded as exiting the grid. The complexity of computing the total number of such paths is simplified by introducing the modulus operation with 10^9 + 7 to handle potentially very large numbers.

Examples

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 <= 50
  • 0 <= maxMove <= 50
  • 0 <= startRow < m
  • 0 <= startColumn < n

Approach and Intuition

To solve this problem efficiently, we can use a dynamic programming (DP) approach that leverages the ability to recursively calculate the number of exit paths based on smaller, previously computed subproblems.

  1. Initialize a DP table where dp[i][j][k] represents the number of ways to reach the cell (i, j) using exactly k moves.
  2. Start with the initial state set at the starting position with dp[startRow][startColumn][0] = 1 since there is one way to be at the start without any moves.
  3. For each move from 1 to maxMove, update the DP table based on the potential moves from each cell:
    • Move up (i-1, j)
    • Move down (i+1, j)
    • Move left (i, j-1)
    • Move right (i, j+1)
  4. For every move when updating the state, consider if moving to or from a boundary cell. If a move takes the ball out of bounds, accumulate those outcomes since they represent valid exit paths.
  5. Since the result can grow large, use modular arithmetic to keep the counts manageable, as specified by the problem with 10^9 + 7.

Through this DP approach alongside boundary checks and accumulation of exit valid paths, we can compute the total number of ways the ball can exit the grid within the specified move limit. This provides a clear and perceptive method to solve the problem by dynamically building upon simpler subproblem solutions.

Solutions

  • Java
java
class Solution {
  public int calculatePaths(int rows, int cols, int maxMove, int startRow, int startCol) {
    int modVal = (int)(1e9 + 7);
    int[][] counts = new int[rows][cols];
    counts[startRow][startCol] = 1;
    int result = 0;
    for (int step = 1; step <= maxMove; step++) {
      int[][] nextCounts = new int[rows][cols];
      for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
          if (i == rows - 1) result = (result + counts[i][j]) % modVal;
          if (j == cols - 1) result = (result + counts[i][j]) % modVal;
          if (i == 0) result = (result + counts[i][j]) % modVal;
          if (j == 0) result = (result + counts[i][j]) % modVal;
          nextCounts[i][j] = (
              ((i > 0 ? counts[i - 1][j] : 0) + (i < rows - 1 ? counts[i + 1][j] : 0)) % modVal +
              ((j > 0 ? counts[i][j - 1] : 0) + (j < cols - 1 ? counts[i][j + 1] : 0)) % modVal
          ) % modVal;
        }
      }
      counts = nextCounts;
    }
    return result;
  }
}

The code provided is a Java solution for calculating the number of possible paths that move out of a grid's boundary. The method calculatePaths uses dynamic programming to keep track of all possible positions on a grid and updates the number of ways to reach each position with each move, up to a specified maximum number of moves.

Follow these insights to understand the implementation:

  • The function parameters include the grid dimensions (rows and cols), the maximum number of allowed moves (maxMove), and the starting position (startRow and startCol) within the grid.
  • An integer result is initiated to accumulate the number of out-of-boundary paths.
  • A 2D array counts is used to store the number of ways to reach each position in the grid. Initially, the start position is set to one.
  • The algorithm iteratively calculates possible moves from each position up to maxMove times while updating path counts using a temporary grid nextCounts.
  • For each cell in nextCounts, check if the current position contributes to an out-of-bound path (i.e., on the boundary) and update result accordingly.
  • For movements to valid grid positions, update path count considering movements from adjacent cells (up, down, left, right).
  • The modulo operation with modVal = 10^9 + 7 ensures the result remains manageable by constraining it within the limits of a 32-bit integer.

Make sure to apply modular arithmetic during each update to prevent overflow and ensure the computations remain within the specified constraints (i.e., the large prime number 10^9 + 7). This solution efficiently tracks path counts without recalculating previously considered configurations, using dynamic updating of the counts per permissible move leading to optimized space and time complexity for large inputs.

Comments

No comments yet.