How Many Ways Across a Blocked Grid
A robot moves from the top-left corner to the bottom-right corner of a grid, going only
RIGHT or DOWN. Cells marked 1 are BLOCKED and cannot be entered. Count the distinct
paths.
Print the count modulo 1000000007.
0 0 0
0 1 0 -> 2
0 0 0
## The recurrence, and the one new line
Problem 532 is this with no obstacles. The recurrence gains a single guard:
blocked -> ways[r][c] = 0
otherwise -> ways[r][c] = ways[r-1][c] + ways[r][c-1]
Setting a blocked cell to 0 rather than skipping it is what matters. Zero is the true count of paths THROUGH that cell, so the recurrence stays correct for everything downstream without any special handling. Skipping it instead leaves whatever was in the array, which in a rolling one-dimensional table is the value from the row above, and paths then leak through the obstacle.
That is the most common bug here and it is silent: the answer is too large by an amount that depends on the obstacle's position.
## The two borders
The FIRST ROW is not all ones any more. Once an obstacle appears, every cell to its right is unreachable:
dp[0] = 1 unless blocked
dp[c] = 0 if blocked, else dp[c-1]
The FIRST COLUMN needs the same treatment on each row, and in the rolling version that is
the line dp[0] = 0 if blocked, which must run before the inner loop.
Forgetting the first column is subtle, because a rolling array carries dp[0] forward
unchanged, so an obstacle in column 0 is ignored entirely. The test 0 0 / 1 1 / 0 0
answers 0 and catches it: the whole middle row is blocked, so nothing gets through.
## Blocked endpoints
If the start or the destination is blocked the answer is 0. The recurrence gives that for
free: a blocked start makes dp[0] zero and everything derived from it zero, and a blocked
destination is set to 0 when it is reached.
1 as a one-cell grid answers 0, and 0 answers 1.
## Cost
Time O(m n). Space O(n).
The closed-form binomial of problem 532 does not survive obstacles, which is the point of having both problems: the formula was faster and the table generalises.