We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Out of Boundary Paths

Difficulty: Medium

Problem Description

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 10^9 + 7.

Key Insights

  • The ball can move in four directions: up, down, left, right.
  • If the ball moves out of the grid, it counts as a valid path.
  • Dynamic programming can be used to keep track of the number of ways to reach each cell in the grid after a certain number of moves.
  • Memoization is useful to avoid recalculating results for the same state.

Space and Time Complexity

Time Complexity: O(maxMove * m * n)
Space Complexity: O(m * n)

Solution

The solution uses dynamic programming to count the number of ways to move the ball out of the grid. We maintain a 2D array that records the number of paths for each cell at a given number of moves. We iterate through the number of moves, updating the paths for each cell based on the possible movements to adjacent cells. The result is accumulated from cells that are out of bounds.

Code Solutions

def findPaths(m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
    MOD = 10**9 + 7
    dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]
    
    # Initial state
    dp[startRow][startColumn][0] = 1
    result = 0
    
    # Iterate through each move
    for moves in range(1, maxMove + 1):
        for i in range(m):
            for j in range(n):
                # Check all four directions
                for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n:
                        dp[i][j][moves] = (dp[i][j][moves] + dp[ni][nj][moves - 1]) % MOD
                    else:
                        result = (result + dp[i][j][moves - 1]) % MOD
    
    return result
← Back to All Questions