63. Unique Paths II
A walker starts on the top-left cell of an m x n grid and wants to reach the bottom-right cell, moving only one cell right or one cell down per step. This time some cells are blocked.
Your function receives the grid as a 2D array of integers where 0 marks an open cell and 1 marks an obstacle. Return the number of distinct routes from the top-left corner to the bottom-right corner that never touch an obstacle.
If the start or the finish cell is itself blocked, no route exists and the answer is 0. The answer is guaranteed to be at most 2 * 10^9.
Example 1:
Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: The blocked center leaves exactly two routes: across the top then down the right edge, or down the left edge then across the bottom.
Example 2:
Input: grid = [[0,1],[0,0]]
Output: 1
Explanation: The obstacle at the top-right forces the single route down first, then right.
Constraints:
- 1 ≤ m, n ≤ 100
- grid[i][j] is 0 or 1
- The answer is at most 2 * 10⁹.
Hints:
Start from the obstacle-free recurrence paths(i, j) = paths(i-1, j) + paths(i, j-1) and add one rule: a blocked cell contributes 0 routes, no matter what its neighbors say.
Be careful with the first row and first column — they are 1 only up to the first obstacle, and 0 everywhere after it.
One row of state is enough: sweeping left to right, set dp[j] = 0 on an obstacle, otherwise dp[j] += dp[j-1].
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Expected output: 2