Walls and Gates

medium graph bfs matrix

Problem

Each cell in an m×n grid is a wall (-1), a gate (0), or empty (INF=2147483647). Fill every empty cell with its distance to the nearest gate.

Inputrooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]

Output[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Multi-source BFS from all gates floods the empty cells in distance order.

grid (rows by ';', cells by ',', I=INF, W=-1, G=0)

from collections import deque
INF = 2147483647
def walls_and_gates(rooms):
    if not rooms: return
    m, n = len(rooms), len(rooms[0])
    q = deque()
    for r in range(m):
        for c in range(n):
            if rooms[r][c] == 0:
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

const INF = 2147483647;
function wallsAndGates(rooms) {
  const m = rooms.length, n = rooms[0].length;
  const q = [];
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (rooms[r][c] === 0) q.push([r, c]);
  while (q.length) {
    const [r, c] = q.shift();
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] === INF) {
        rooms[nr][nc] = rooms[r][c] + 1;
        q.push([nr, nc]);
      }
    }
  }
}

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int INF = 2147483647, m = rooms.length, n = rooms[0].length;
        Deque q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
            if (rooms[r][c] == 0) q.add(new int[]{ r, c });
        int[][] d = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] dd : d) {
                int nr = p[0] + dd[0], nc = p[1] + dd[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
                    rooms[nr][nc] = rooms[p[0]][p[1]] + 1;
                    q.add(new int[]{ nr, nc });
                }
            }
        }
    }
}

void wallsAndGates(vector>& rooms) {
    int INF = 2147483647, m = rooms.size(), n = rooms[0].size();
    queue> q;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
        if (rooms[r][c] == 0) q.push({r, c});
    int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == INF) {
                rooms[nr][nc] = rooms[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
}

Explanation

We want every empty room to hold its distance to the nearest gate. A naive approach would BFS outward from each empty cell, but that repeats work. The smarter idea is multi-source BFS: start from all gates at once and flood outward together.

We first scan the grid and push every gate (value 0) into the queue. Because BFS expands in layers, all cells one step from any gate get filled before any cell two steps away, so the first time a cell is reached, that is its shortest distance.

For each cell popped, we look at its four neighbors. If a neighbor is still INF (untouched empty room), we set it to the current cell's distance plus one and enqueue it. Walls (-1) and already-filled cells are skipped.

Using INF as the "not visited yet" marker is the trick that keeps it clean: a cell gets written exactly once, so there's no need for a separate visited set.

Example: with gates at the top and bottom-left, the flood spreads simultaneously, and a cell squeezed between two gates simply takes whichever wave reaches it first, giving the smaller distance.

Time: O(mn) Space: O(mn)