Level 1 Desk to nearest bathroom
An office floor plan is a list of equal-length strings. Each character is one cell:
B: a bathroomD: a desk.: open floor#: a wall (can't be entered)
You move one cell up, down, left or right per step. You may walk through bathrooms, desks and open floor.
Write desk_distances(grid: list[str]) -> list[int]. It returns, for every desk in row-major order (top row first, left to right), the fewest steps from that desk to any bathroom. Use -1 for a desk that can't reach a bathroom. An empty grid, or a grid with no desks, gives [].
Grids can be up to about 400 × 400 cells and full of desks. A separate search from every desk is too slow, so aim for O(rows × cols) in total.
desk_distances([
"D.#B",
"..#.",
"B..D",
])
# desks in row-major order: (0,0) and (2,3)
# (0,0) -> bathroom (2,0): 2 steps
# (2,3) -> bathroom (0,3): 2 steps
# => [2, 2]
Show hint
Search outward from the bathrooms instead of from the desks, from all of them at once.