Out of Boundary Paths
Medium · Dynamic Programming · Dynamic Programming
Problem
A ball sits at cell [startRow, startColumn] of an m x n grid. In one move you push it to one of the four neighboring cells (up, down, left or right); a push across the edge sends it out of the grid.
You may make at most maxMove moves. Return the number of distinct move sequences that end with the ball leaving the grid, modulo 10^9 + 7. A sequence stops as soon as the ball leaves.
Examples
Input: m = 1, n = 3, maxMove = 1, startRow = 0, startColumn = 1 Output: 2
In a single row the ball leaves by moving up or down; left and right keep it inside.
Input: m = 3, n = 3, maxMove = 2, startRow = 1, startColumn = 1 Output: 4
From the center the first move reaches an edge cell, and from each of the four edge cells exactly one move exits.
Input: m = 2, n = 3, maxMove = 0, startRow = 0, startColumn = 0 Output: 0
With no moves allowed the ball cannot leave.
Constraints
- 1 <= m, n <= 50
- 0 <= maxMove <= 50
- 0 <= startRow < m
- 0 <= startColumn < n
Approaches
- Recount from scratch for each exit move — time O(maxMove² · m · n), space O(m · n)
Follow-up
Can you instead count the sequences of exactly maxMove moves that never leave the grid, or handle cells the ball cannot enter? Both change only where a count is allowed to flow.
Related problems
Start free on Cariara · Coding problems · System design studio
