Roadworks on the Grid
A bike courier works in a part of town where the streets form a neat grid. The depot is at the top-left intersection and today's customer is at the bottom-right one. To never waste time, she only ever rides east (right) or south (down).
This week some intersections are fenced off for roadworks and cannot be ridden through. She likes to vary her ride. How many different routes does she have?
Your task
Write countRoutes(grid). grid[r][c] is 0 for an open intersection and 1 for one closed by roadworks. Return the number of different routes from grid[0][0] to the bottom-right cell that move one cell right or one cell down at a time and never enter a closed cell.
If the depot or the customer's intersection is closed, return 0. A 1 × 1 open grid has exactly 1 route (she is already there).
countRoutes(grid: int[][]) → int
Examples
grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
2
With no roadworks a 3 × 3 grid has 6 routes. The closed middle kills every route through it, leaving two: all the way right then down, or all the way down then right.
grid = [[0, 0, 0, 0], [0, 0, 1, 0], [1, 0, 0, 0]]
3
Count how many ways reach each corner, row by row. The first row is all 1s. The second row is 1, 2, 0 (closed), 1. The third row is 0 (closed), 2, 2, 3. So 3 routes reach the customer.
Constraints
- 1 ≤ number of rows, number of columns ≤ 20
- Every row has the same length.
- grid[r][c] is 0 or 1.
Start with brute force
Explore every route with recursion: from each cell, try going right and try going down, and count the times you reach the customer.
On an open 20 × 20 grid there are over 35 billion routes, and the recursion visits each one. Most of the work repeats: every route that passes through the same middle cell recounts everything after it.
Hints
0 of 4 shown- Hint 1
Pick any open intersection that is not on the top row or the left edge. From which two intersections could the courier have arrived there?
- Hint 2
She arrived from the one above or the one to the left. Routes through those two never overlap, so the routes to this cell = routes to the cell above + routes to the cell on the left.
- Hint 3
A closed intersection has 0 routes into it. What about the top row: does every cell there have 1 route, even if there is a closed cell further left?
- Hint 4
Fill a table row by row, left to right. Set the start to 1 if it is open. For every other cell: 0 if closed, otherwise (value above, or 0 off the grid) + (value to the left, or 0 off the grid). One row of values is enough if you update it in place.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every route into a cell comes from the cell above or the cell on the left, and those two groups of routes are different. So routes(r, c) = routes(r - 1, c) + routes(r, c - 1), and a closed cell has 0.
Trace the second example, row by row:
- Row 0, all open:
1, 1, 1, 1. Each cell can only be reached from its left. - Row 1: column 0 gets 1 from above. Column 1 gets 1 + 1 = 2. Column 2 is closed, so 0. Column 3 gets 1 (above) + 0 (left) = 1. Row:
1, 2, 0, 1. - Row 2: column 0 is closed, 0. Column 1 gets 2 + 0 = 2. Column 2 gets 0 + 2 = 2. Column 3 gets 1 + 2 = 3.
The answer is 3. The code keeps only one row: before you update ways[c], it still holds the value from the row above, so adding ways[c - 1] (already updated, the cell on the left) gives exactly above + left.
function countRoutes(grid) {
const cols = grid[0].length;
const ways = new Array(cols).fill(0); // ways[c] = routes into column c of the current row
ways[0] = grid[0][0] === 0 ? 1 : 0;
for (const row of grid) {
for (let c = 0; c < cols; c++) {
if (row[c] === 1) ways[c] = 0; // closed: no routes through here
else if (c > 0) ways[c] += ways[c - 1]; // from above (old value) + from the left
}
}
return ways[cols - 1];
}def count_routes(grid):
cols = len(grid[0])
ways = [0] * cols # ways[c] = routes into column c of the current row
ways[0] = 1 if grid[0][0] == 0 else 0
for row in grid:
for c in range(cols):
if row[c] == 1:
ways[c] = 0 # closed: no routes through here
elif c > 0:
ways[c] += ways[c - 1] # from above (old value) + from the left
return ways[cols - 1]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.