Given a grid where 1 represents an obstacle and 0 represents a free cell, return the number of monotonic paths from the top-left to the bottom-right cell using only right and down moves. Pattern focus: Obstacles. The recurrence is the same as Unique Paths, but blocked cells contribute zero ways.
grid contains 0 for free cells and 1 for obstacles
number of valid paths
Example 1:
Input:
grid = [[0,0,0],[0,1,0],[0,0,0]]
Output:
2
Explanation:
The obstacle blocks the center, leaving 2 valid routes.
Example 2:
Input:
grid = [[0,1],[0,0]]
Output:
1
Explanation:
Only one path remains because the top-right cell is blocked.
Example 3:
Input:
grid = [[1]]
Output:
0
Explanation:
If the starting cell is blocked, no path exists.