Given an m x n grid where some cells contain obstacles (1) and the rest are empty (0), count the number of distinct paths from the top-left corner to the bottom-right corner. The robot may move only right or down, and cannot enter an obstacle cell. If the start or end cell is an obstacle, the answer is 0.
Input
obstacleGrid: 2D array where 0 = empty cell and 1 = obstacle
Output
The number of unique paths from (0,0) to (m-1,n-1).
Examples
Example 1
InputobstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output2
Explanation: A 3x3 grid with one obstacle in the middle. The two paths go around the obstacle: down-down-right-right and right-right-down-down.
Example 2
InputobstacleGrid = [[0,1],[0,0]]
Output1
Constraints
1 <= m, n; obstacleGrid[i][j] is 0 or 1.
Moves are restricted to right and down.