Routes Around Roadblocks
Easy2-D Dynamic ProgrammingFree
Problem
A city map is given as a grid where grid[r][c] is 0 for an open intersection and 1 for a roadblock. A cyclist starts at the top-left intersection and wants to reach the bottom-right one, moving only right or down and never entering a roadblock.
Return the number of different routes. If the start or the destination is itself a roadblock, there are no routes.
Example 1
- Input:
- grid = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]]
- Output:
- 4
Without the roadblock there would be 10 routes; the 6 that pass through cell (1, 2) are lost.
Example 2
- Input:
- grid = [[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0]]
- Output:
- 1
The only way down the middle row is through column 2: right, right, down, down, right.
Constraints
- 1 ≤ grid.length, grid[0].length ≤ 100
- grid[r][c] is 0 or 1
- The answer fits in a 32-bit signed integer.
Hint
Show the first hint
Start from the plain route-counting recurrence: routes into a cell = routes into the cell above + routes into the cell to the left.
Walkthrough
How to approach it
01Clarify before coding
- What if the start is blocked? Then the answer is 0; the same for the destination.
- Moves are only right and down? Yes, so no cell is visited twice and there are no cycles.
- Does the first row still count as 1 everywhere? Only up to the first roadblock; every cell after it in that row is unreachable.
02Brute force
DFS from the start trying right and down, skipping roadblocks, and count arrivals at the destination.
Cost: Exponential: up to C(m + n - 2, m - 1) routes (about 6 · 10^8 on an open 17 × 17 grid), each walked one by one.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.