> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0286-walls-and-gates.md).

# 0286. Walls and Gates

<https://leetcode.com/problems/walls-and-gates>

## Description

You are given an `m x n` grid `rooms` initialized with these three possible values.

* `-1` A wall or an obstacle.
* `0` A gate.
* `INF` Infinity means an empty room. We use the value `231 - 1 = 2147483647` to represent `INF` as you may assume that the distance to a gate is less than `2147483647`.

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`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/03/grid.jpg)

```
**Input:** rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
**Output:** [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
```

**Example 2:**

```
**Input:** rooms = [[-1]]
**Output:** [[-1]]
```

**Example 3:**

```
**Input:** rooms = [[2147483647]]
**Output:** [[2147483647]]
```

**Example 4:**

```
**Input:** rooms = [[0]]
**Output:** [[0]]
```

**Constraints:**

* `m == rooms.length`
* `n == rooms[i].length`
* `1 <= m, n <= 250`
* `rooms[i][j]` is `-1`, `0`, or `231 - 1`.

## ac1: BFS

```java
class Solution {
    public void wallsAndGates(int[][] rooms) {
        // edge case
        if (rooms.length == 0 || rooms[0].length == 0) return;

        Queue<int[]> q = new LinkedList<int[]>();
        int row = rooms.length;
        int col = rooms[0].length;

        // walk, get gates
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (rooms[r][c] == 0) q.offer(new int[] {r, c});
            }
        }

        // BFS
        int layer = 0;
        while (!q.isEmpty()) {
            layer++;
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int[] head = q.poll();
                int r = head[0]; int c = head[1];

                if (r < row-1 && rooms[r+1][c] > layer) {
                    rooms[r+1][c] = layer;
                    q.offer(new int[] {r+1, c});
                }
                if (r > 0 && rooms[r-1][c] > layer) {
                    rooms[r-1][c] = layer;
                    q.offer(new int[] {r-1, c});
                }    
                if (c < col-1 && rooms[r][c+1] > layer){
                    rooms[r][c+1] = layer;
                    q.offer(new int[] {r, c+1});
                } 
                if (c > 0 && rooms[r][c-1] > layer) {
                    rooms[r][c-1] = layer;
                    q.offer(new int[] {r, c-1});
                }
            }
        }
    }
}

/**
walk, get 0s
BFS, if val > layer, set val = layer, offer to queue
**/
```