Unique Paths with Obstacles
easyDynamic Programming II+10 XPTime limit 2s
A robot starts at the top-left cell of an r × c grid and wants to reach the bottom-right cell, moving only right or down. Some cells are blocked (#); the robot can never enter them. How many different paths are there? Print the count modulo 1 000 000 007.
Input:
- line 1:
r c - next
rlines:ccharacters each,.(free) or#(blocked), no spaces
Output: the number of paths modulo 10⁹ + 7 (0 if the start or the end is blocked).
Constraints: 1 ≤ r, c ≤ 500.
Think about it: same as plain Unique Paths — ways[i][j] = ways[i−1][j] + ways[i][j−1] — except that a blocked cell has 0 ways. Take the modulo at every addition.
Sample input 1
3 3 ... .#. ...
Sample output 1
2
Sample input 2
2 2 .# ..
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).