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  INFINF INF INF  -1INF  -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

这题比较有意思，要求算出空房间到门的最近距离。

直觉BFS，之前看到谷歌面经求二维矩阵上的最短距离，这题类似。一个比较naive的做法是，先找出所有门，然后对每个门做BFS，二维矩阵上的DFS和BFS一般需要使用hashset或者visited矩阵来判断是否已经遍历过。但是这题在计算距离时可以根据距离的大小判断是否重复遍历。已经在一次BFS里遍历过了，再到这里的距离肯定大于之前的距离。 所以不做更新。代码如下：

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 rooms:            return        m = len(rooms)        n = len(rooms[0])        queue = collections.deque()        walls = []        for i in xrange(m):            for j in xrange(n):                if rooms[i][j] == 0:                    walls.append((i,j))        dx = [1, 0, -1, 0]        dy = [0, -1, 0, 1]        for wall in walls:            queue.append(wall)            while queue:                cur = queue.popleft()                for j in xrange(4):                    x = dx[j] + cur[0]                    y = dy[j] + cur[1] #rooms[cur[0]][cur[1]] < rooms[x][y] - 1判断是否在此次BFS重复遍历，或早是否此次BFS得不到最短距离。

if x >= 0 and x < m and y >= 0 and y < n and rooms[x][y] > 0 and rooms[cur[0]][cur[1]] < rooms[x][y] - 1 :                 　　rooms[x][y] = rooms[cur[0]][cur[1]] + 1                 　　queue.append((x,y)) return

这种做法其实有很大的冗余存在，我们完全可以利用BFS的性质，做一个有多个起点的BFS。也就是多个门开始放在一个queue里。利用BFS的性质，第一个处理到空房间的，肯定是最短距离，代码如下：

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 rooms:            return        m = len(rooms)        n = len(rooms[0])        queue = collections.deque()        walls = []        for i in xrange(m):            for j in xrange(n):                if rooms[i][j] == 0:                    queue.append((i,j))        dif = [0, 1, 0, -1, 0]        INT_MAX = 2**31 - 1           while queue:            cur = queue.popleft()            for j in xrange(4):                x = dif[j] + cur[0]                y = dif[j+1] + cur[1]                if 0 <= x < m and  0 <= y < n and rooms[x][y] > 0 and rooms[x][y] == INT_MAX : ＃第一次处理                    rooms[x][y] = rooms[cur[0]][cur[1]] + 1                    queue.append((x,y))        return

第一种解法平均复杂度为O(k*n^2),k为门的数目，最差时间复杂度为O(n^4)。而第二种解法的平均和最差复杂度都是O(n^2)

具体见这个帖子：