Loading page…
Practice problem · easy
A ride-hailing app shows a city as a grid of blocks. A driver starts at the top left block and drives to the bottom right block. The streets are one-way, so every move goes one block right or one block down. Some blocks are closed for road works.
Your team lead asks: "How many different routes can the driver take?"
Write count_routes(grid).
grid is a list of equal-length strings. . is an open block and # is a closed block.Input: grid = ["....", ".#..", "...."]
Output: 4Let routes[r][c] be the number of routes from the start to block (r, c). A closed block has 0. An open block adds the routes that arrive from above and from the left: routes[r][c] = routes[r - 1][c] + routes[r][c - 1].
The start has 1 route. Fill the table row by row, left to right.
| Row | Column 0 | Column 1 | Column 2 | Column 3 |
|---|---|---|---|---|
| 0 | 1 (start) | 1 (left 1) | 1 (left 1) | 1 (left 1) |
| 1 | 1 (above 1) | 0 (closed) | 1 (above 1 + left 0) | 2 (above 1 + left 1) |
| 2 | 1 (above 1) | 1 (above 0 + left 1) | 2 (above 1 + left 1) | 4 (above 2 + left 2) |
The finish holds 4, so there are 4 routes.
Input: grid = [".", ".", "."]
Output: 1One column means one road straight down.
Input: grid = ["...", "###", "..."]
Output: 0A full row of closed blocks cuts the city in two.
1 ≤ rows ≤ 25 and 1 ≤ columns ≤ 25, and every row has the same length. or #There are only 625 blocks, but the routes are many: with every road open, a 25 by 25 grid has 32,247,603,683,100 routes. Listing them one by one never finishes. A table with one entry for each block costs 625 steps, and the answer still fits in a 64-bit integer.
count_routes · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.