Python BFS Solution


  • -1
    def wallsAndGates(self, rooms):
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        queue, visited = deque([]), set()
        level = 1
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r,c))
        while queue:
            size = len(queue)
            for i in range(size):
                r, c = queue.popleft()
                visited.add((r,c))
                # top
                if r-1 >= 0 and rooms[r-1][c] != -1 and level < rooms[r-1][c] and (r-1,c) not in visited:
                    rooms[r-1][c] = level
                    queue.append((r-1, c))
                # right
                if c+1 < len(rooms[0]) and rooms[r][c+1] != -1 and level < rooms[r][c+1] and (r,c+1) not in visited:
                    rooms[r][c+1] = level
                    queue.append((r, c+1))
                # bot
                if r+1 < len(rooms) and rooms[r+1][c] != -1 and level < rooms[r+1][c] and (r+1, c) not in visited:
                    rooms[r+1][c] = level
                    queue.append((r+1, c))
                # left
                if c-1 >= 0 and rooms[r][c-1] != -1 and level < rooms[r][c-1] and (r, c-1) not in visited:
                    rooms[r][c-1] = level
                    queue.append((r, c-1))
            level += 1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.