BFS, clean python code


  • 0
    class Solution(object):
        def wallsAndGates(self, rooms):
            if not rooms:
                return
    
            m, n = len(rooms), len(rooms[0])
            for i in xrange(m):
                for j in xrange(n):
                    if rooms[i][j] != 0:
                        continue
    
                    queue, distance = [(i, j)], 1
                    while queue:
                        for _ in xrange(len(queue)):
                            x, y = queue.pop(0)
                            for row, col in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
                                newX, newY = x + row, y + col
    
                                if not (0 <= newX < m and 0 <= newY < n) or rooms[newX][newY] in [-1, 0] or distance >= rooms[newX][newY]:
                                    continue
    
                                rooms[newX][newY] = distance
                                queue.append((newX, newY))
                        distance += 1

Log in to reply
 

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