# Walls and Gates

## Problem

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQcwSRVUxlMpuENjrce%2F-MQiqeqd9SKGYXksVnWf%2FScreen%20Shot%202021-01-10%20at%205.31.10%20PM.png?alt=media\&token=8c420499-cd55-437d-8c6d-8a4b9ae040ce)

### Thought Process

* We are going to pay attention to the '0' cells and apply BFS to find neighboring INF values

* BFS covers all neighbors and then moves forward

* Adding all the gates ('0') into the queue gurantees that all the updated values is the minimal value to the nearest target. A good way to think about it is below:

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQcwSRVUxlMpuENjrce%2F-MQiroY7245oGOidH71F%2FScreen%20Shot%202021-01-10%20at%205.36.15%20PM.png?alt=media\&token=105a0f70-d1a7-43ec-bef5-a9cdb64d0a12)

* BFS:
  \*
  1. Store all 0's in a queue
  2. Pull the 0's from the queue and check if the neighbors are INF then update

## Solution

```
from collections import deque
class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        q = deque()
        
        if rooms is None:
            return 
        
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    q.append([i,j])
                    
        direc = [[1,0], [-1,0],[0,-1], [0,1]]  
        
        while q:
            level_size = len(q)
            
            for _ in range(level_size):  
                coor = q.popleft()
                row = coor[0]
                col = coor[1]
                
                for i in direc:
                    newX = row+i[0]
                    newY = col+i[1]
                    
                    if newX < 0 or newX >= len(rooms) or newY < 0 or newY >= len(rooms[0]):
                        continue 
                    if rooms[newX][newY] == 2147483647:   
                        rooms[newX][newY] = rooms[row][col] + 1
                        q.append([newX, newY])
                    
            
                
```

## Time Complexity

* **Time:** O(m\*n)
* **Space:** O(m\*n)