from collections import deque

INF = 2**31 - 1

def walls_and_gates(rooms):
    rows = len(rooms)
    cols = len(rooms[0]) if rows else 0
    queue = deque((r, c) for r in range(rows) for c in range(cols)
                  if rooms[r][c] == 0)
    while queue:
        r, c = queue.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] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))
    return rooms