How many ways down through the grid

A grid has 0 for an open cell and 1 for a blocked one. Starting at the top left and finishing at the bottom right, moving only right or down, count how many different routes there are. A route may not pass through a blocked cell.

If the start or the finish is blocked, the answer is 0.

Worked example#

0 0 0
0 1 0
0 0 0

Without the obstacle there would be six routes. The blocked middle cell rules out four of them, leaving 2: across the top then down the right, or down the left then across the bottom.

The idea#

Counting routes is the same shape as finding the cheapest one, with two changes: you add instead of taking a minimum, and a blocked cell contributes nothing.

Every route into a cell arrives from above or from the left, and those two sets of routes are entirely separate: one ends by stepping down, the other by stepping right, so no route is counted twice.

ways[r][c] = ways[r-1][c] + ways[r][c-1]

A blocked cell gets 0, which is not a special case so much as the truth: no route reaches the far side through it, so it contributes nothing to either neighbour.

The start gets 1, because there is exactly one way to be standing where you started: do nothing.

Watch the first row and column#

Without obstacles the first row and column are all 1. With them, a blocked cell stops everything after it in that row or column, because there is only one way in.

Writing the rule uniformly, treating anything off the grid as 0, handles that on its own. Special-casing the edges is where the bugs live.

Why the routes are never listed#

For a 15 by 15 grid there are about 40 million routes. The table has 225 cells. Each cell's count is worked out once and used by the two cells it feeds, and that reuse is the whole reason a number that large can be produced without ever building a single route.

Constraints#

• 1 <= rows, columns <= 20
• The answer fits in a signed 64-bit integer