Blocked cells count for nothing
Same counting recurrence, except a blocked cell always contributes zero ways. About 11 minutes.
A road is closed
Back to counting routes, but some blocks are closed for roadworks. The robot can't enter them.
The rule for an open block doesn't change: routes from above plus routes from the left. A closed block is simpler still. Nobody can arrive there, so it has 0 routes, whatever its neighbours say.
Edges first: one path each along the top row and the left column (no obstacles there).
The zero does the work for you
You never have to ask "is there a closed road somewhere between here and the start?" The 0 in a closed block gets added into every box after it, just like any other number. Anything that could only be reached through the roadworks ends up with fewer routes, automatically.
In a 3 × 3 city with the middle block closed, just 2 routes survive: around the top, and around the bottom.
if grid[r][c] == 1:
ways[r][c] = 0 # closed: no way inA block is closed. The block above it has 4 routes and the block to its left has 3. How many routes reach the closed block?
- A0
- B7
- C3
Show the answer
0. Nobody can enter a closed block, so it has 0 routes whatever its neighbours have.
Paths with obstacles
You get a grid of 0s and 1s, where 1 marks an obstacle. Return how many distinct paths lead from the top-left corner to the bottom-right corner, moving only right or down and never onto an obstacle. If the start or end cell is itself an obstacle, return 0.
grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]] → 2
1 ≤ rows, cols ≤ 20 · each cell is 0 or 1 · return a long