Paths That Stay Inside
A token starts at cell (sr, sc) and makes EXACTLY k moves, each one step up, down,
left or right. Every move must land inside the grid. Count the move sequences.
Print the count modulo 1000000007.
2 x 2, k = 2, start (0,0) -> 4
1 x 1, k = 1, start (0,0) -> 0 every move leaves
## The complement of problem 541
541 counts the sequences that ESCAPE within at most N moves. This counts the sequences
that never escape in exactly k moves. The same forward sweep answers both, and what
changes is what gets accumulated and when the answer is read.
541 add to a running total whenever a move leaves; answer = that total
542 discard moves that leave; answer = sum of the FINAL layer
Being able to switch between them by changing those two lines is the point of having both.
## The sweep
cur[sr][sc] = 1
repeat k times:
next = zeros
for every cell with cur[r][c] > 0:
for each of the four directions:
if the target is inside: next[nr][nc] += cur[r][c]
cur = next
answer = sum of cur
## Exactly k, so read the final layer
The answer is the sum of the LAST layer, not a running total. Every sequence counted has
made exactly k legal moves and is somewhere in the grid at the end.
Summing across layers instead would count sequences of every length up to k, which is a
different question, and one that has no natural reading here since a token that has made
fewer moves is not finished.
## Two boundaries
k = 0 answers 1: the empty sequence is one sequence, and the token is at its start. A
solution that returns 0 for no moves is claiming the empty sequence does not exist.
1 x 1 with k = 1 answers 0: the grid is a single cell and all four moves leave it, so
no legal sequence of length 1 exists.
Those two bracket the counting convention from both ends.
## Why the count needs a modulus
Each step multiplies the number of sequences by up to 4, so k = 50 allows up to 4^50,
which is about 10^30. The modulus is not decoration.
## Cost
Time O(k m n). Space O(m n) with two layers.