Grid Routes Avoiding Blocks

Given a grid of 0s and 1s where 1 marks a blocked cell, count the number of distinct paths from the top-left cell to the bottom-right cell moving only right or down, never entering a blocked cell. Return 0 if the start or end is blocked.

Examples

in: grid = [[0,0,0],[0,1,0],[0,0,0]]

out: 2

two ways around the center block

in: grid = [[0,1],[0,0]]

out: 1

down then right

Constraints

1 <= rows, cols <= 100
grid[i][j] is 0 or 1

Hints

target: O(rows * cols) time⌘↩ run · ⇧⌘↩ submit