Solutions

# DFS, BFS, or multisource BFS. Start from gates and fill in the distance to the nearest gate. Use a queue to keep track of the cells we need to process, and a set to keep track of the cells we have already visited. 
# graphs

# Multisource BFS - O(m*n) time, O(m*n) space
def wallsAndGates(rooms: list[list[int]]) -> None:
    ROWS = len(rooms)
    COLS = len(rooms[0])

    from collections import deque
    q = deque()
    visited = set()

    # Start from all gates at the same time
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0:
                q.append((r,c))
                visited.add((r,c))

    def add_room(r, c):
        if r < 0 or r == ROWS or c < 0 or \
            c == COLS or (r,c) in visited or \
            rooms[r][c] == -1:
            return
        q.append((r,c))
        visited.add((r,c))

    dist = 0
    while q:
        for _ in range(len(q)):
            r, c = q.popleft()
            rooms[r][c] = dist # update distance as we pop from the queue
            add_room(r+1,c)
            add_room(r-1,c)
            add_room(r,c+1)
            add_room(r,c-1)
        dist += 1


# BFS - O((m*n)^2) time, O(m*n) space
def wallsAndGatesBFS(rooms: list[list[int]]) -> None:
    ROWS = len(rooms)
    COLS = len(rooms[0])

    from collections import deque

    def bfs(r, c):
        q = deque()
        q.append((r,c))
        visited = set()
        visited.add((r,c))
        dist = 0

        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                if rooms[r][c] == 0:
                    rooms[r][c] = dist
                    return
                add_room(r+1,c)
                add_room(r-1,c)
                add_room(r,c+1)
                add_room(r,c-1)
            dist += 1

        def add_room(r, c):
            if r < 0 or r == ROWS or c < 0 or \
                c == COLS or (r,c) in visited or \
                rooms[r][c] == -1:
                return
            q.append((r,c))
            visited.add((r,c))
            
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 2147483647:
                bfs(r, c)


# DFS with backtracking - O(m*n*4^(m*n)) time, O(m*n) space
def wallsAndGatesDFS(rooms: list[list[int]]) -> None:
    ROWS, COLS = len(rooms), len(rooms[0])
    INF = 2147483647
    visit = [[False for _ in range(COLS)] for _ in range(ROWS)]

    def dfs(r, c):
        if (r < 0 or c < 0 or r >= ROWS or
            c >= COLS or rooms[r][c] == -1 or
            visit[r][c]):
            return INF
        if rooms[r][c] == 0:
            return 0

        visit[r][c] = True
        res = INF
        res = min(res, 1 + dfs(r+1, c))
        res = min(res, 1 + dfs(r-1, c))
        res = min(res, 1 + dfs(r, c+1))
        res = min(res, 1 + dfs(r, c-1))
        visit[r][c] = False # backtrack
        return res

    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == INF:
                rooms[r][c] = dfs(r, c)