Walls and Gates

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1373/

BFS Template Solution

from collections import deque
class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        INF = 2147483647
        queue = deque()
        dirs = [(-1,0),(1,0),(0,1),(0,-1)]
        m = len(rooms)
        if m == 0:
            return
        n = len(rooms[0])
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i,j))

        while queue:
            x,y = queue.popleft()
            for d in dirs:
                newX, newY = x+d[0],y+d[1]
                if 0 <=newX < m and 0 <=newY < n and rooms[newX][newY] == INF:
                    rooms[newX][newY] = rooms[x][y]+1
                    queue.append((newX,newY))