Paths Out of the Grid
A ball starts at cell (sr, sc) of an m by n grid. Each move takes it one step up,
down, left or right. Count the move sequences of length AT MOST N that take the ball OUT
of the grid. Once it leaves, it stops.
Print the count modulo 1000000007.
2 x 2, N = 2, start (0,0) -> 6
1 x 3, N = 3, start (0,1) -> 12
## Counting forwards, not backwards
The natural recursion asks, from a cell with k moves left, how many ways to get out. That
works.
The forward version is easier to roll: carry how many ways the ball can BE at each cell after
t moves, and accumulate exits as they happen.
cur[sr][sc] = 1
repeat N times:
next = zeros
for each cell with cur[r][c] > 0:
for each of the four directions:
inside -> next[nr][nc] += cur[r][c]
outside -> total += cur[r][c]
cur = next
Each of the N rounds needs only the previous round, so two grids suffice rather than
N + 1 of them. That is the space rolling this problem is filed under, and here it is the
difference between O(N m n) memory and O(m n).
## Why exits are accumulated rather than stored
A path that leaves at move t is finished; it cannot contribute again later. So its count
is added to the running total at the moment it exits and then dropped from the grid.
Trying to keep exited paths in the table instead requires an extra absorbing state and gets double counted if the absorbing cell is ever propagated, which is a common way to get an answer that is too large.
## At most N, not exactly N
The total is accumulated across all N rounds, so shorter escapes are included
automatically. Reading only the final round would count exactly-N paths, which is a
different question.
1 x 1 with N = 1 answers 4 and with N = 2 answers 4 as well: all four first moves
leave immediately, nothing remains inside, and the second round adds nothing. That pair is
the test for the at-most reading, since a solution counting exactly N answers 0 on the
second.
## Boundaries
N = 0 answers 0: no moves, no escapes. A 3 by 3 grid starting at the centre with N = 1
also answers 0, since every single move stays inside.
1 x 2 with N = 3 answers 9, which is small enough to enumerate by hand and is worth
doing once to confirm the accumulation.
## Cost
Time O(N m n). Space O(m n).