LC 0286 [M] Walls and Gates - ALawliet/algorithms GitHub Wiki

start from gates 0, use traversal to fill nearby rooms with distances if not OOB and condition passes (all pretty much the same thing):

• rooms[nr][nc] > rooms[r][c] # greater than 0 (gate) or -1 (wall)
• rooms[nr][nc] == 2147483647 # is empty INF
• not rooms[nr][nc] == -1 and rooms[nr][nc] == 2147483647 # is not -1 (wall) and is empty

we want to fill the EMPTY rooms, so start BFS from each GATEs

GATE = 0
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
EMPTY = 2147483647

class Solution(object):
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        ROWS, COLS = len(rooms), len(rooms[0])
        Q = deque()
        
        for r in range(ROWS):
            for c in range(COLS):
                if rooms[r][c] == GATE:
                    Q.append((r, c))

        while Q:
            r, c = Q.popleft()
            for dr, dc in DIRS:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == EMPTY:
                    rooms[nr][nc] = rooms[r][c] + 1
                    Q.append((nr, nc))