Tường Và Cổng

from collections import deque
def walls_and_gates_opt(rooms):
    ROWS, COLS = len(rooms), len(rooms[0])
    q = deque()
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0: q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == 2147483647:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

def walls_and_gates_brute(rooms):
    ROWS, COLS = len(rooms), len(rooms[0])
    def dfs(r, c, dist):
        if r < 0 or r == ROWS or c < 0 or c == COLS or rooms[r][c] < dist:
            return
        rooms[r][c] = dist
        dfs(r + 1, c, dist + 1)
        dfs(r - 1, c, dist + 1)
        dfs(r, c + 1, dist + 1)
        dfs(r, c - 1, dist + 1)
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0:
                dfs(r, c, 0)