loading

Walls and Gates — Step-by-Step Visualization

mediumLeetCode #286ArrayBreadth-First SearchMatrix

You are given an `m x n` grid `rooms` initialized with three possible values: `-1` (a wall or an obstacle), `0` (a gate), and `2147483647` (INF, representing an empty room). Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with `INF`.

Algorithm Pattern

Multi-Source BFS

Key Idea

Instead of performing BFS from every empty room (which is slow), we can perform a single BFS starting from ALL gates simultaneously. All gates are at distance 0. Their neighbors are at distance 1, and so on. This 'wave' ensures that each room is updated with its shortest distance to any gate precisely once.

Step-by-Step Approach

  1. Initialize a queue `q` with the coordinates of all gates `(r, c)`.
  2. While `q` is not empty:
  3. Pop `(r, c)` and check its 4 neighbors.
  4. If a neighbor is an INF room:
  5. Update `rooms[nr][nc] = rooms[r][c] + 1`.
  6. Add `(nr, nc)` to the queue.

Common Gotchas

  • Don't start BFS from empty rooms; that would be O(N²M²) instead of O(NM).
  • Walls (-1) should be completely ignored.

Related Problems

← All problems