[Leetcode] Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Last time when I attempted at this problem, I tried to find the distance between each empty room to the closest gate. I have a feeling that I re-computed many things. Take above example, when I computed (0,0) to the closest gate, I will for sure go through (1, 0), (2, 0) and then reach (3, 0) which is a gate. But, thinking this way, it's very hard to record the intermediate results and reconcile when there is a conflict. For example, (1,1)'s closest gate is not (3, 0), but (0, 2). How to decide?

It turns out thinking this problem in a flipped way can solve all these confusions in a natural way. Instead of calculating the closest gate for each room, we can start from the gate, and grow the distance field through breadth-first search (BFS). Due to the nice property of BFS, whenever we reach a empty room, then it must be the shortest distance to the gate. For example, a room is 2 steps away from gate 1, and 4 steps away from gate 2. Then when we are in the level 2, this room will be added in the queue through gate 1's path.

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 any(rooms): return 
        queue = []
        
        m, n = len(rooms), len(rooms[0])
        
        for i in xrange(m):
            for j in xrange(n):
                if rooms[i][j] == 0:
                    queue.append(((i, j), 0))
        queue = collections.deque(queue)
        
        # lambda function speeds up the program a lot
        is_empty = lambda x, y: 0<=x<m and 0<=y<n and rooms[x][y]>=2147483647 
        
        while queue:
            (x, y), dist = queue.pop()
            
            if is_empty(x-1, y):
                rooms[x-1][y] = dist + 1
                queue.appendleft(((x-1, y), dist+1))
            if is_empty(x+1, y):
                rooms[x+1][y] = dist + 1
                queue.appendleft(((x+1, y), dist+1))
            if is_empty(x, y-1):
                rooms[x][y-1] = dist + 1
                queue.appendleft(((x, y-1), dist+1))
            if is_empty(x, y+1):
                rooms[x][y+1] = dist + 1
                queue.appendleft(((x, y+1), dist+1))