Basic BFS in Python


  • 0
    class Solution(object):
        def wallsAndGates(self, rooms):
            """
            :type rooms: List[List[int]]
            :rtype: void Do not return anything, modify rooms in-place instead.
            """
            if not rooms:
                return
            m, n = len(rooms), len(rooms[0])
            for i in range(len(rooms)):
                for j in range(len(rooms[0])):
                    if rooms[i][j] == 0:
                        queue = [(i,j)]
                        level = 1
                        while queue:
                            new_queue = []
                            for x, y in queue:
                                if x+1 < m and rooms[x+1][y] > level:
                                    rooms[x+1][y] = level
                                    new_queue.append((x+1,y))
                                if x-1 >= 0 and rooms[x-1][y] > level:
                                    rooms[x-1][y] = level
                                    new_queue.append((x-1,y))
                                if y+1 < n and rooms[x][y+1] > level:
                                    rooms[x][y+1] = level
                                    new_queue.append((x,y+1))
                                if y-1 >= 0 and rooms[x][y-1] > level:
                                    rooms[x][y-1] = level
                                    new_queue.append((x,y-1))
                            level += 1
                            queue = new_queue

Log in to reply
 

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