Unique Paths II
You are given an m x n integer matrix obstacleGrid. A robot starts at the top-left corner of the grid, obstacleGrid[0][0], and wants to reach the bottom-right corner, obstacleGrid[m - 1][n - 1].
The robot can only move either down or right at any point in time.
Some cells contain obstacles:
0means the cell is empty and can be visited.1means the cell contains an obstacle and cannot be visited.
Return the number of unique paths the robot can take to reach the bottom-right corner without moving through obstacles.
Example 1
0 0 0 0 1 0 0 0 0
Input
obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]Output
2There are two valid paths around the obstacle in the middle cell.
Example 2
0 1 0 0
Input
obstacleGrid = [[0,1],[0,0]]Output
1The only valid path is to move down first and then right.
Constraints
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] is 0 or 1
- The answer will be less than or equal to 2 * 10^9