228. Grid Paths with Obstacles
MediumDynamic ProgrammingGrid
Count the right/down paths from the top-left to the bottom-right cell, avoiding obstacles (1). Print the count modulo 10⁹ + 7.
Input format
Line 1: r c Next r lines: c values (0 = free, 1 = obstacle)
Output format
The number of paths mod 10⁹ + 7.
Example 1
Input
3 3 0 0 0 0 1 0 0 0 0
Output
2
Example 2
Input
2 2 0 1 0 0
Output
1
Constraints
1 ≤ r, c ≤ 500
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…