A flood-response map is a grid of R rows and C columns. Each cell is either open (marked 0) or sandbagged and impassable (marked 1). A crew member starts at the top-left cell and must reach the bottom-right cell, moving on each step to the cell immediately to the right or immediately below, and may only stand on open cells.
Count how many distinct right/down routes avoid every sandbagged cell. If the top-left or bottom-right cell is itself sandbagged, there are no valid routes.
Line 1: two integers R and C.
Next R lines: each contains C integers, each 0 (open) or 1 (sandbagged).
A single integer: the number of right/down routes from the top-left cell to the bottom-right cell that pass only through open cells.
Example 1
Input
3 3 0 0 0 0 1 0 0 0 0
Expected
2
Explanation
The center is blocked, leaving two routes: one hugging the top and right edges, one hugging the left and bottom edges.
Example 2
Input
2 2 0 0 0 0
Expected
2
Explanation
With no obstacles in a 2x2 grid there are two routes: right-then-down and down-then-right.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →