Walls and Gates

Problem

You are given an m x n grid of integers describing a building. Each cell is one of three things: a wall (-1), a gate (0), or an empty room, encoded as a very large value INF = 2^31 - 1. Overwrite every empty room with the number of steps to its nearest gate, moving only up/down/left/right and never through walls. Rooms from which no gate is reachable keep the value INF. Modify the grid in place.

• The building has at most 200 rows and 200 columns.
• Cell values are -1, 0, or INF.

Examples

• Input

    0  INF  -1  INF
  INF  INF  INF  INF
  INF   -1  INF   -1
  INF  INF  INF    0

  becomes

    0    1   -1    5
    1    2    3    4
    2   -1    2   -1
    3    2    1    0

  The room at (0,3) is 5 steps from its nearest gate because the wall at (2,3) blocks the direct column down to the gate at (3,3), forcing a detour through (1,2) and (3,2).
• [[INF]] stays [[INF]]: no gate at all.
• [[0, INF, INF]] becomes [[0, 1, 2]].

Hints

1. Each room needs the distance to the closest gate. Which search visits cells in increasing order of distance from a start point?
2. Searching from every room separately is expensive. What if you searched outward from the gates instead?
3. Multi-source BFS: enqueue all gates at distance 0, expand level by level, and assign each room the level at which it is first reached.