Python BFS


  • 0
    import collections
    class Solution(object):
        def wallsAndGates(self, rooms):
            if not rooms:
                return 
            INF, h, w, dir, queue = 2147483647, len(rooms), len(rooms[0]), [[0, 1], [0, -1], [1, 0], [-1, 0]], collections.deque()
            for i in xrange(h):
                for j in xrange(w):
                    if rooms[i][j] == 0:
                        queue.append((i, j))
            while queue:
                top = queue.popleft()
                y, x = top[0], top[1]
                for i in xrange(len(dir)):
                    ty, tx = y +  dir[i][0], x + dir[i][1]
                    if 0 <= tx < w and 0 <= ty < h and rooms[ty][tx] == INF:
                        rooms[ty][tx] = rooms[y][x] + 1
                        queue.append((ty, tx))
    

Log in to reply
 

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