A pollen grain drifts across a greenhouse panel modeled as a grid of R rows and C columns. Each cell is open (0) or blocked by a strut (1). Starting at the top-left cell, the grain drifts to the bottom-right cell; from cell (r, c) it may move to (r, c+1), (r+1, c), or (r+1, c+1), and may only land on open cells.
Count how many distinct routes reach the bottom-right cell landing only on open cells. If the top-left or bottom-right cell is blocked, there are no valid routes.
Line 1: two integers R and C.
Next R lines: each contains C integers, each 0 (open) or 1 (blocked).
A single integer: the number of right/down/diagonal routes from the top-left cell to the bottom-right cell that land only on open cells.
Example 1
Input
2 2 0 0 0 0
Expected
3
Explanation
From the top-left open cell there are three routes to the bottom-right: right-then-down, down-then-right, and the single diagonal move.
Example 2
Input
2 2 0 1 1 0
Expected
1
Explanation
Both orthogonal neighbours of the start are blocked, so the only route is the diagonal move straight to the bottom-right: 1 route.
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 →