A building's floor plan is a grid of integers:
-1is a wall;0is an emergency exit;2147483647(that is,2**31 - 1) is an open room.
People move one cell at a time up, down, left or right, through exits and open rooms but never through walls. Write fill_distances(grid) that modifies grid in place, replacing each open room's value with the number of steps from that room to the closest exit. Rooms that can't reach any exit keep 2147483647; walls and exits are unchanged. The function returns nothing.
W, E, R = -1, 0, 2147483647
grid = [
[R, R, W, E],
[E, W, R, R],
[R, R, R, W],
[W, R, R, R],
]
fill_distances(grid)
grid
# [[ 1, 2, -1, 0],
# [ 0, -1, 2, 1],
# [ 1, 2, 3, -1],
# [-1, 3, 4, 5]]
grid = [[R, W], [W, E]]
fill_distances(grid)
grid # [[2147483647, -1], [-1, 0]] (the top-left room is walled in)
Constraints: up to 300 × 300 cells, with any number of exits (possibly none). Aim for O(rows · cols): searching from every room separately, or from every exit one after another, is too slow for the tests.
Show hint
Rather than asking "which exit is closest to this room?", let the search spread outward from all the exits together, one step at a time; the first time it reaches a room is the answer for that room.