Unique Paths with Obstacles
Count unique paths from top-left to bottom-right of a grid that contains obstacles.
Input format
The first line contains R and C. The next R lines contain 0/1 grid (0 = empty, 1 = obstacle; start/end are 0).
Output format
Print the number of unique paths from top-left to bottom-right.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
7 3
0 0 1
0 1 0
1 1 1
0 0 0
0 1 0
0 0 1
0 0 0Expected output
0Example 2
Input
8 2
0 1
0 0
0 1
0 1
1 1
1 0
0 0
1 0Expected output
0