Walls and Gates (BFS)

LeetCode 286

class Solution:
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        Example:
        INF  -1  0  INF
        INF INF INF  -1
        INF  -1 INF  -1
          0  -1 INF INF
        Res:
          3  -1   0   1
          2   2   1  -1
          1  -1   2  -1
          0  -1   3   4
        """
        if not rooms:
            return
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    que = collections.deque([(i-1, j, 1),(i+1, j, 1),(i, j-1, 1),(i, j+1, 1)])
                    while que:
                        x, y, val = que.popleft()
                        if x<0 or x>len(rooms)-1 or y<0 or y>len(rooms[0])-1 or rooms[x][y] <= val:
                            continue
                        rooms[x][y] = val
                        que.extend([(x-1,y,val+1),(x+1,y,val+1),(x,y-1,val+1),(x,y+1,val+1)])