Python simple BFS


  • 0
    A
    from collections import deque
    class Solution(object):
    
        def wallsAndGates(self, rooms):
            """
            :type rooms: List[List[int]]
            :rtype: void Do not return anything, modify rooms in-place instead.
            """
            
            for i in range(len(rooms)):
                for j in range(len(rooms[0])):
                    if rooms[i][j] == 0:
                        self.search(rooms, i, j)
     
        def search(self, rooms, i, j):
            
            directions = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
            qu = deque()
            for x,y in directions: qu.append((x,y,1)) 
            while qu:
                p, q, c = qu.popleft()
                if 0 <= p < len(rooms) and 0 <= q < len(rooms[0]) and rooms[p][q] > c:
                    rooms[p][q] = c
                    directions = [(p+1,q),(p-1,q),(p,q+1),(p,q-1)]
                    for x,y in directions: qu.append((x,y,c+1))
    

Log in to reply
 

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