Walls and Gates

BFS

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.

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:

• 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)