Skills101
← All coding problems

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 r lines: c characters 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).

Loading editor…

Log in to run and submit your code — it's free.