# 286 Walls and Gates

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:

``````_ # G _   3 # 0 1
_ _ _ #   2 2 1 #
_ # _ #   1 # 2 #
G # _ _   0 # 3 \$

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

Constraints:

• `m == rooms.length`
• `n == rooms[i].length`
• `1 <= m, n <= 250`
• `rooms[i][j]` is `-1`, `0`, or `231 - 1`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 `````` ``````from collections import deque class Solution: INF = 2147483647 def wallsAndGates(self, rooms: List[List[int]]) -> None: """ Do not return anything, modify rooms in-place instead. """ m = len(rooms) n = len(rooms[0]) q = deque() for i in range(m): for j in range(n): if rooms[i][j] == 0: q.append((i, j)) ''' Each gate only looks at the areas within 1 space before we check the next gate. So each area within one space of the gates are checked for rooms and these rooms are marked, then added to the queue. Once all gates are checked, each new space is checked, and so forth. So, once a room gets hit, it has to be from the closest gate. ''' while q: x, y = q.popleft() for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]: r = x + d[0] c = y + d[1] if ( r < 0 or r >= m or c < 0 or c >= n or rooms[r][c] != self.INF ): continue q.append((r, c)) rooms[r][c] = rooms[x][y] + 1``````