# LeetCode 286: Walls and Gates

## Problem Restatement

We are given an `m x n` grid called `rooms`.

Each cell has one of three values:

| Value | Meaning |
|---|---|
| `-1` | Wall or obstacle |
| `0` | Gate |
| `2147483647` | Empty room, also called `INF` |

We need to fill each empty room with the distance to its nearest gate.

Distance is the number of steps needed to reach a gate by moving only up, down, left, or right.

If an empty room cannot reach any gate, it should remain `INF`.

The problem uses `2147483647` as `INF`, and assumes every reachable distance is smaller than that value.

## Input and Output

| Item | Meaning |
|---|---|
| Input | 2D integer grid `rooms` |
| Output | Nothing |
| Mutation | Modify `rooms` in-place |
| Wall | `-1` |
| Gate | `0` |
| Empty room | `2147483647` |

Function shape:

```python
class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        ...
```

## Examples

For:

```python
INF = 2147483647

rooms = [
    [INF, -1,  0, INF],
    [INF, INF, INF, -1],
    [INF, -1, INF, -1],
    [0,   -1, INF, INF],
]
```

The result should be:

```python
[
    [3, -1, 0, 1],
    [2,  2, 1, -1],
    [1, -1, 2, -1],
    [0, -1, 3, 4],
]
```

The top-left room gets value `3` because the nearest gate is three steps away:

```python
(0, 0) -> (1, 0) -> (2, 0) -> (3, 0)
```

The room at `(0, 3)` gets value `1` because it is next to the gate at `(0, 2)`.

## First Thought: BFS From Every Empty Room

A direct solution is to run BFS from each empty room until we find the nearest gate.

For each `INF` cell:

1. Start a BFS from that room.
2. Search outward level by level.
3. Stop when we reach a gate.
4. Write that distance into the room.

This is correct because BFS finds the shortest path in an unweighted grid.

But it repeats a lot of work.

If there are many empty rooms, each BFS may scan a large part of the grid again.

## Problem With Repeated BFS

Let the grid have `m` rows and `n` columns.

There are up to `m * n` empty rooms.

A BFS from one room can also visit up to `m * n` cells.

So repeated BFS can cost:

```python
O((m * n) * (m * n))
```

That is too expensive.

We need one BFS that computes all distances together.

## Key Insight

Instead of starting BFS from every empty room, start BFS from every gate at the same time.

This is called multi-source BFS.

All gates begin with distance `0`.

Then BFS expands outward:

| BFS Layer | Meaning |
|---|---|
| Distance `0` | Gates |
| Distance `1` | Empty rooms next to a gate |
| Distance `2` | Empty rooms two steps from a gate |
| Distance `3` | Empty rooms three steps from a gate |

The first time BFS reaches an empty room, it must be through the nearest gate, because BFS expands in increasing distance order.

This fills every reachable room exactly once.

## Algorithm

Create a queue.

Scan the whole grid.

Whenever we find a gate:

```python
rooms[r][c] == 0
```

push its coordinates into the queue.

Then run BFS.

For each cell popped from the queue:

1. Check its four neighbors.
2. Ignore neighbors outside the grid.
3. Ignore walls.
4. Ignore gates or rooms that already have a distance.
5. For each unvisited empty room, set:

```python
rooms[nr][nc] = rooms[r][c] + 1
```

6. Push that neighbor into the queue.

Because `INF` means unvisited empty room, we do not need a separate `visited` array.

## Correctness

All gates are inserted into the queue before BFS begins, and each gate has distance `0`.

BFS processes cells in increasing distance order. So when an empty room is reached for the first time, the path used to reach it has the smallest possible number of steps from any gate.

The algorithm writes a distance only when the cell is still `INF`. After that, the room is never updated again.

This is correct because the first written distance is already the shortest distance. Any later path would be at the same distance or longer, since BFS expands level by level.

Walls are never entered, so all paths counted by the algorithm are valid grid paths.

Rooms that cannot be reached from any gate are never visited, so they remain `INF`.

Therefore, after BFS finishes, every reachable empty room contains its shortest distance to the nearest gate, and every unreachable empty room remains `INF`.

## Complexity

Let:

```python
R = number of rows
C = number of columns
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * C)` | Each cell is pushed and processed at most once |
| Space | `O(R * C)` | The queue may contain many cells |

## Implementation

```python
from collections import deque

class Solution:
    def wallsAndGates(self, rooms: list[list[int]]) -> None:
        if not rooms or not rooms[0]:
            return

        rows = len(rooms)
        cols = len(rooms[0])
        INF = 2147483647

        queue = deque()

        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= rows:
                    continue

                if nc < 0 or nc >= cols:
                    continue

                if rooms[nr][nc] != INF:
                    continue

                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))
```

## Code Explanation

We handle an empty grid first:

```python
if not rooms or not rooms[0]:
    return
```

Then we store the grid size:

```python
rows = len(rooms)
cols = len(rooms[0])
```

The problem uses this value for empty rooms:

```python
INF = 2147483647
```

We collect every gate into the queue:

```python
if rooms[r][c] == 0:
    queue.append((r, c))
```

This is the multi-source part. BFS starts from all gates together.

The four possible moves are:

```python
directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]
```

During BFS, we pop one cell:

```python
r, c = queue.popleft()
```

Then we inspect its neighbors.

If a neighbor is outside the grid, skip it.

If a neighbor is not `INF`, skip it.

That means we skip walls, gates, and already-filled rooms:

```python
if rooms[nr][nc] != INF:
    continue
```

For each unvisited empty room, we write the distance:

```python
rooms[nr][nc] = rooms[r][c] + 1
```

Then we push it into the queue so it can expand to its neighbors.

## Testing

```python
def test_walls_and_gates():
    s = Solution()
    INF = 2147483647

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

    s.wallsAndGates(rooms)

    assert rooms == [
        [3, -1, 0, 1],
        [2,  2, 1, -1],
        [1, -1, 2, -1],
        [0, -1, 3, 4],
    ]

    rooms = [[0]]
    s.wallsAndGates(rooms)
    assert rooms == [[0]]

    rooms = [[INF]]
    s.wallsAndGates(rooms)
    assert rooms == [[INF]]

    rooms = [
        [INF, -1],
        [-1,  0],
    ]
    s.wallsAndGates(rooms)
    assert rooms == [
        [INF, -1],
        [-1,  0],
    ]

    print("all tests passed")

test_walls_and_gates()
```

Test meaning:

| Test | Why |
|---|---|
| Standard grid | Checks multi-source shortest distances |
| Single gate | No room needs filling |
| Single empty room | No reachable gate, remains `INF` |
| Blocked room | Walls prevent reaching the gate |