Maintained by Vikas Dulgunde, software engineer
You are handed a grid of `0`s and `1`s. A `0` marks an open cell you can stand on, and a `1` marks a blocked cell you must avoid. A traveler begins at the top-left cell and wants to reach the bottom-right cell.
On each move the traveler may step one cell to the right or one cell down, nothing else. There is no moving up, left, or diagonally, so every route is a monotone walk toward the lower-right.
Your job is to return the number of complete routes that reach the destination without ever landing on a blocked cell. If the start or the destination itself is blocked, no valid route exists and the answer is zero.
The grid always has at least one cell. The single-cell grid counts as one route when it is open and zero routes when it is blocked.
The only block sits in the middle. A route can hug the top edge then the right edge, or hug the left edge then the bottom edge. Both skirt the obstacle, giving two routes.
The top-right cell is blocked, so going right first is a dead end. The traveler must go down, then right, which is the single surviving route.
The starting cell is itself blocked, so the traveler cannot even begin. There are no valid routes.
Visible test cases
The number of ways to reach a cell only depends on the two neighbours directly above it and directly to its left, since those are the only cells that can lead into it.
A blocked cell contributes zero ways to anything downstream, so set its count to 0 instead of summing its neighbours.
You never look at the row above the previous one, so a single rolling array of width n is enough to carry the counts forward row by row.
Define a function that returns the route count from a given cell to the destination, branching into the right move and the down move, and let recursion explore every walk.
Fill route counts in reading order so that by the time you reach a cell, its top and left neighbours are already known, and reuse one array across rows to keep memory flat.