533. 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.

Constraints - `1 ≤ m ≤ 100` - `1 ≤ n ≤ 100` - every value is `0` or `1`