Routes across a grid with blocked cells

Dynamic programming Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
row = [0] * 3
row[0] = 1
for cells in grid:
    for c, blocked in enumerate(cells):
        if blocked:
            row[c] = 0
        elif c:
            row[c] += row[c - 1]
print(row[-1])

Options260

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2

Right: with the centre blocked, only the routes along the edges remain.

Zeroing a blocked cell stops any count from flowing through it, which is the only change from the open-grid version.

Why not the others?

B 6. That is the count for an open 3 × 3 grid.
C 0. The two edge routes avoid the block.

Route counts filled into a grid one cell at a time, each open cell adding the counts above and to its left, blocked cells shown as 0, for two grids.

Steps come from running the Python solution.

Text version

3 × 4 grid, one block:

3 × 4 grid, one block: finished table
Row	0	1	2	3
0	1	1	1	1
1	1	✕ 0	1	2
2	1	1	2	4

Answer: 4 in cell (2, 3), from (1, 3) and (2, 2).

2 × 3 grid, corner block:

2 × 3 grid, corner block: finished table
Row	0	1	2
0	1	1	✕ 0
1	1	2	2

Answer: 2 in cell (1, 2), from (0, 2) and (1, 1).

30-second answer

Each open cell can be entered only from above or from the left, so routes[r][c] = routes[r - 1][c] + routes[r][c - 1], and blocked cells hold 0. The start holds 1 unless it is blocked. Fill row by row: O(R × C) time, and one row of memory, O(C), is enough.

Practise saying it · 45 s. No recording, just a timer

Explain counting routes around blocks.

Say your answer out loud, then check which of these points you covered:

routes = above + left
Blocked cells are 0
O(R × C), one row

Deep dive

This is the grid-DP template: each cell combines a fixed set of earlier neighbours.

Without blocks the answer is C(R + C - 2, R - 1), a nice check.

One row works because each cell reads the cell above (old value) and to its left (new value).

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def count_routes(grid: list[list[int]]) -> int:
    row = [0] * len(grid[0])  # routes into each column, this row
    row[0] = 1
    for cells in grid:
        for c, blocked in enumerate(cells):
            if blocked:
                row[c] = 0  # nothing passes through a block
            elif c:
                row[c] += row[c - 1]  # from above (old) + from left
    return row[-1]

Common mistakes

Forgetting that a blocked start or end means zero routes.
Filling the first row as all 1s even after a block.

Senior take & follow-ups

Explain why one row is enough; it is a common follow-up.

Follow-up questions

Think of your answer first, then open the hint.

What if moves can also go diagonally?
Show hint
Add the up-left neighbour to the sum.
How do you find the cheapest route instead?
Show hint
Replace the sum with min plus the cell's cost.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.