Unique Paths with Obstacles

Problem Statement

A robot is located at the top-left corner of an m x n grid. The robot can only move either down or right at any point in time.

The grid contains obstacles marked as 1, while empty cells are marked as 0. The robot cannot step on obstacles.

Return the number of possible unique paths from the top-left corner to the bottom-right corner.

Input Format

Line 1: An integer representing the number of rows. Following lines: Space-separated integers (0 or 1) representing each row of the grid.

Output Format

A single integer representing the number of unique paths.

Examples

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output: 2

There's one obstacle in the middle. The two paths are:

• Right → Right → Down → Down
• Down → Down → Right → Right

Example 2:

Input:
[[0,1],
 [0,0]]

Output: 1

The only path goes Down → Right.

Constraints

• m == obstacleGrid.length
• n == obstacleGrid[0].length
• 1 ≤ m, n ≤ 100
• obstacleGrid[i][j] is 0 or 1