1136. Unique Paths II — With Obstacles

A robot moves only right or down on a grid where 1 marks an obstacle and 0 is free. Return the number of distinct paths from the top-left to the bottom-right, avoiding obstacles (0 if the start or end is blocked). The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the number of unique paths.

Examples

Input: {"grid":[[0,0,0],[0,1,0],[0,0,0]]}
Output: 2
Explanation: Two paths avoid the center obstacle.

Input: {"grid":[[0,1],[0,0]]}
Output: 1
Explanation: One path.

Input: {"grid":[[0]]}
Output: 1
Explanation: Single free cell.

Constraints

• 1<=rows,cols<=100

Asked by