Unique Paths II (Robot Paths with Blocked Cells)

Medium

Description

A robot stands in the top-left cell of a grid. It wants to reach the bottom-right cell. At each step it can move only one cell down or one cell right.

The grid obstacleGrid has 0 for a free cell and 1 for a blocked cell. The robot cannot step on a blocked cell.

Return how many different paths the robot can take from the top-left to the bottom-right cell. If there is no path, return 0.

Examples

Example 1:

Input: obstacleGrid = [[0,0],[0,0]]
Output: 2
Explanation: No cell is blocked: right-down and down-right are the two paths.

Example 2:

Input: obstacleGrid = [[0,1,0],[0,0,0]]
Output: 1
Explanation: The robot must go down first, then right twice.

Example 3:

Input: obstacleGrid = [[0,0,0],[0,0,1]]
Output: 0
Explanation: The goal cell is blocked, so there is no path.

Array
Dynamic Programming
Matrix

Constraints

obstacleGrid[i][j] is either 0 or 1.
1 <= obstacleGrid.length <= 100
1 <= obstacleGrid[i].length <= 100
All rows of obstacleGrid have the same length.

Examples

3 shown

Example 1

Input

[[0,0],[0,0]]

Output

Example 2

Input

[[0,1,0],[0,0,0]]

Output

Example 3

Input

[[0,0,0],[0,0,1]]

Output

Opening the editor...