Unique Paths with Obstacles
A robot starts at the top-left corner of an m x n grid and can only move down or right at any point in time.
Cells holding a 1 are obstacles and cells holding a 0 are empty. The robot cannot step on an obstacle. Return the number of unique paths from the top-left corner to the bottom-right corner.
Input & Output
Input
obstacle_grid — the grid, where 1 marks an obstacle and 0 marks an empty cell
Output
the number of unique obstacle-free paths from the top-left cell to the bottom-right cell
Example
Input
obstacle_grid = [[0,0,0],[0,1,0],[0,0,0]]
Output
2
Explanation
The obstacle sits in the middle, so the robot must go around it: Right → Right → Down → Down, or Down → Down → Right → Right. Without the obstacle the same grid would have six paths.
Example
Input
obstacle_grid = [[0,1],[0,0]]
Output
1
Explanation
The obstacle at the top-right blocks the Right → Down route, leaving only Down → Right.
Constraints
m == obstacle_grid.length,n == obstacle_grid[0].length1 <= m, n <= 100obstacle_grid[i][j]is0or1