Coding - Out of Boundary Paths

Problem Statement: Out of Boundary Paths

Problem Description

There is an m x n grid with a ball. The ball starts at [startRow, startColumn]. On each move, the ball can move to an adjacent cell in one of four directions: up, down, left, or right. Return the number of paths that move the ball out of the grid boundary in at most maxMove moves. Because the answer can be very large, return it modulo 10^9 + 7.

Constraints

• 1 <= m, n <= 10^4
• 0 <= startRow < m
• 0 <= startColumn < n
• 0 <= maxMove <= 10^4

Examples

1. Example 1:

   • Input: m = 2, n = 2, startRow = 0, startColumn = 0, maxMove = 2
   • Output: 3
   • Explanation: The ball can move in four different paths: right, right-up, up, and up-left.
   • Example 1 Explanation: The ball can move in four different paths: right, right-up, up, and up-left.

2. Example 2:

   • Input: m = 1, n = 2, startRow = 0, startColumn = 0, maxMove = 3
   • Output: 1
   • Explanation: The ball will definitely go out of the grid after 1 move.
   • Example 2 Explanation: The ball will definitely go out of the grid after 1 move.

Hints

• Consider using dynamic programming to solve this problem. You can use a 2D array dp where dp[i][j][k] represents the number of ways to reach cell (i, j) using k moves.
• Initialize the dp array with zeros and set dp[startRow][startColumn][0] = 1 since there is one way to start at the initial position.
• For each move from 0 to maxMove - 1, update the dp array by considering the four possible moves from each cell.
• After maxMove moves, sum up all the values in the dp array that are not on the boundary of the grid and return the result modulo 10^9 + 7.

This problem tests your understanding of dynamic programming and how to model a problem with a 3D array to keep track of the number of ways to reach each cell using a certain number of moves.