leetcode-graph

286. Walls and Gates.py

class Solution:
    """
    
    Thought Process:
        grid coordinates/matrix --> It's definitely graph problem.
            -each cell(x,y) is node in the graph
            -it's directed graph, path exist only rooms[next_i][next_j] > rooms[i][j]
                (-1 is wall)
        Brute Force
            For each cell, we do dfs to find distance to shortest gate.
            O(n^2)
        BFS:
            We do bfs on gate instead of each cell. To progressively fill the empty cell with level.
            Because -1 is obstacle, so the edge exist when rooms[next_i][next_j] > rooms[i][j], and rooms[next_i][next_j] =  rooms[i][j]+1, then put neighbor in the queue
                
    Note:
    1. Since BFS guarantees that we search all rooms of distance d before searching rooms of distance d + 1, the distance to an empty room must be the shortest.
    2. Once we set a room's distance, we are basically marking it as visited, which means each room is visited at most once. Therefore, the time complexity does not depend on the number of gates and is O(mn).
    """
    directions = [(-1,0),(1,0),(0,1),(0,-1)]
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        BFS
        T:O(mn) because each room is visited at most once
        S:O(mn) because of queue
        """
        m = len(rooms)
        n = len(rooms[0])
        # step1: start bfs on empty room
        q = collections.deque([])
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    q.append((i,j))
        # step2:
        while q:
            i, j = q.popleft()
            for direction in self.directions:
                next_i, next_j = i+direction[0], j+direction[1]
                if 0<=next_i<m and 0<=next_j<n and rooms[next_i][next_j] > rooms[i][j]:
                    rooms[next_i][next_j] =  rooms[i][j]+1
                    q.append((next_i,next_j))