Given a grid with blocked cells, return the number of ways to move from the top-left cell to the bottom-right cell using only right and down moves. Pattern focus: Obstacles. This is the counting version of obstacle-aware grid DP.
0 means open cell and 1 means blocked cell
number of valid paths
Example 1:
Input:
grid = [[0,0,0],[0,0,0],[0,0,0]]
Output:
6
Explanation:
A 3x3 open grid has 6 monotonic paths.
Example 2:
Input:
grid = [[0,1,0],[0,0,0],[0,0,0]]
Output:
3
Explanation:
Blocking one cell reduces the count to 3.
Example 3:
Input:
grid = [[0,0,1],[0,0,0],[1,0,0]]
Output:
4
Explanation:
Two obstacles restrict the available routes to 2.