# LeetCode 286: Walls And Gates — Step-by-Step Visual Trace

**Medium** — BFS | Matrix | Graph

## The Problem

Fill each empty room with the distance to its nearest gate, where rooms are represented by a 2D grid with gates (0), walls (-1), and empty rooms (INF).

## Approach

Use multi-source BFS starting from all gates simultaneously. For each gate, perform BFS to explore neighboring empty rooms, updating each room with the minimum distance to any gate encountered so far.

**Time:** O(m * n * g) · **Space:** O(m * n)

## Code

```python
class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return

        rows, cols = len(rooms), len(rooms[0])
        gates = [(i, j) for i in range(rows) for j in range(cols) if rooms[i][j] == 0]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for gate_row, gate_col in gates:
            visited = set()  # To track visited cells in BFS
            queue = deque([(gate_row, gate_col, 0)])

            while queue:
                row, col, distance = queue.popleft()
                rooms[row][col] = min(rooms[row][col], distance)
                visited.add((row, col))

                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc

                    if (
                        0 <= new_row < rows
                        and 0 <= new_col < cols
                        and rooms[new_row][new_col] != -1
                        and (new_row, new_col) not in visited
                    ):
                        queue.append((new_row, new_col, distance + 1))
                        visited.add((new_row, new_col))
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0286_walls-and-gates)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0286_walls-and-gates) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*