01 Matrix

这题注意查重就好，而且其实可以看到此题有明显的DP特征，不过这里DP需要两遍，一遍左上，一遍右下

class Solution(object):
    def updateMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(matrix)
        if not n:
            return []

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

        for i in xrange(n):
            for j in xrange(m):
                if matrix[i][j]:
                    self.BFS(i, j, n, m, matrix)

        return matrix

    def BFS(self, i, j, n, m, matrix):
        queue = collections.deque([(i, j, 0, )])
        checker = set((i, j,))
        while queue:
            row, col, step = queue.pop()
            if matrix[row][col] == 0:
                matrix[i][j] = step
                return 

            for curRow, curCol in [[row + 1, col], [row - 1, col], [row, col + 1], [row, col - 1]]:
                if 0 <= curRow < n and 0 <= curCol < m and (curRow, curCol, ) not in checker:
                    queue.appendleft((curRow, curCol, step + 1))
                    checker.add((curRow, curCol, ))