Walls and Gates

BFS的题，无非就是需要考虑两点，一是顺序需不需要严格有序，或者说严格有序是否能避免额外查重，额外空间和额外逻辑，如果这些满足，我们则需要严格有序即利用队列来解决问题，如果不需要，一般情况下用stack也是可以实现BFS的，第二点则是需要考虑这个BFS应该从起点开始做BFS好还是从终点开始做好，有些问题因为数据的占比不平衡，有时候从某一侧出发进行搜索会明显强于从另外一侧出发，例如这道题，明显门的数量是远远小于空间的数量的，所以我们应该通过门来BFS找到各个位置和离它最近的门的距离，另外这里注意可以站人的空间都是INF，所以我们可以利用这一点省去一个查重矩阵，因为任何不等于INF的位置要不是墙，要不是门，要不就是已经被遍历过了

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        n = len(rooms)
        if not n:
            return 

        m = len(rooms[0])
        if not m:
            return 

        class Point:
            def __init__(self, row, col):
                self.row = row
                self.col = col

        q = collections.deque([])
        direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]
        for i in xrange(n):
            for j in xrange(m):
                if rooms[i][j] == 0:
                    q.appendleft([Point(i, j), 0])

        while q:
            node, step = q.pop()
            if step < rooms[node.row][node.col]:
                rooms[node.row][node.col] = step

            for i, j in direction:
                curRow, curCol = node.row + i, node.col + j
                if 0 <= curRow < n and 0 <= curCol < m:
                    if rooms[curRow][curCol] == 2147483647:
                        q.appendleft([Point(curRow, curCol), step + 1])

另外这道题是严格按照顺序的BFS，且我们必须把所有起点一起纳入同时进行BFS才能保证正确，下面使用namedtuple写的版本

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        n = len(rooms)
        if not n:
            return 

        m = len(rooms[0])
        if not m:
            return 

        Point = collections.namedtuple('Point', ['x', 'y'])
        queue = collections.deque([[Point(i, j), 0] for i in xrange(n) for j in xrange(m) if rooms[i][j] == 0])

        while queue:
            node, step = queue.pop()
            if step < rooms[node.x][node.y]:
                rooms[node.x][node.y] = step
            for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                curRow, curCol = node.x + i, node.y + j
                if 0 <= curRow < n and 0 <= curCol < m:
                    if rooms[curRow][curCol] == 2147483647:
                        queue.appendleft([Point(curRow, curCol), step + 1])

一种更优雅更加Pythonic的写法

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 or not rooms[0]:
            return 

        n, m = len(rooms), len(rooms[0])
        Point = collections.namedtuple('Point', ['x', 'y'])
        queue = [(Point(i, j), 0) for i in xrange(n) for j in xrange(m) if not rooms[i][j]]
        queue = collections.deque(queue)

        while queue:
            node, distance = queue.pop()
            for i, j in [(0, 1,), (1, 0,), (-1, 0,), (0, -1,)]:
                row, col = node.x + i, node.y + j
                if 0 <= row < n and 0 <= col < m:
                    if rooms[row][col] != -1 and distance + 1 < rooms[row][col]:
                        rooms[row][col] = distance + 1
                        queue.appendleft((Point(row, col), distance + 1))