A ball starts at (startRow, startCol) on an rows × cols grid. Each move steps it one
cell up/down/left/right. Moving off the grid edge counts as escaping. Return the
number of distinct move sequences that let the ball escape in at most maxMoves
moves.
breakingBoundaries(rows, cols, maxMoves, startRow, startCol)
Input format: rows cols | startRow startCol | maxMoves.
2x2, start=(0,0), maxMoves=2 // → 6
1x3, start=(0,1), maxMoves=1 // → 2
At every step, the ball has up to four moves, building a sequence before possibly escaping — branching that grows exponentially with maxMoves if enumerated directly (up to 4^maxMoves). Is there shared structure across sequences to avoid redoing work?
You don't need to list every sequence, just count them. Define the subproblem as "how many ways to escape from here, with this many moves left" — that quantity doesn't care about the path taken to arrive, only the current position and remaining budget matter for everything after.
Two different paths arriving at the same cell with the same moves remaining are in an identical position going forward — the future sequences leading to escape are exactly the same. That's the overlapping-subproblem structure memoization exploits.
Two base cases: off the grid already means one successful escape, contributing 1 and consuming no additional moves. On the grid with no moves left means no escape possible, contributing 0.
Otherwise, the ball can step to any of four neighbors (possibly off-grid, which is how escape happens). The count from the current cell is the sum, over all four neighbors, of ways to escape from there with one fewer move. Summing, not maxing, is correct since each neighbor is a genuinely distinct first move, and the problem counts distinct sequences.
Without caching, the same (row, column, moves-remaining) triple gets recomputed repeatedly as different sequences pass through the same cell with the same budget — exponential blowup. Memoizing on the triple computes each subproblem once, reused for every sequence revisiting it.
At most O(rows · cols · maxMoves) distinct triples, each O(1) work beyond four cached lookups — O(maxMoves · rows · cols) total, a massive improvement over naive exponential enumeration.
def breaking_boundaries(rows, cols, max_moves, start_row, start_col):
memo = {}
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def ways(r, c, m):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 1
if m == 0:
return 0
key = (r, c, m)
if key in memo:
return memo[key]
total = 0
for dr, dc in dirs:
total += ways(r + dr, c + dc, m - 1)
memo[key] = total
return total
return ways(start_row, start_col, max_moves)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.