mediumDynamic Programming 2DAI-applied~35 min
Count Ways an Agent Exits the Grid in N Moves
A grid-world agent starts at a cell and may step in four directions. Count how many distinct move sequences of at most maxMove steps carry it off the grid boundary — an episode-termination count.
Problem
Given an m x n grid and a ball starting at (startRow, startColumn), in one move the ball can go up, down, left, or right by one cell, including off the boundary. Return the number of distinct paths of at most maxMove moves that take the ball out of the grid, modulo 1e9+7.
Input
Integers m, n, maxMove, startRow, startColumn.
Output
An integer: the count of out-of-boundary paths modulo 1e9+7.
Constraints
- 1 <= m, n <= 50
- 0 <= maxMove <= 50
- 0 <= startRow < m, 0 <= startColumn < n
Examples
Example 1
Input
m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output
6
Six distinct paths of length at most 2 exit the 2x2 grid.
Example 2
Input
m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output
12
Twelve paths exit within three moves.