题目描述：

LeetCode 542. 01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

题目大意：

给定01矩阵，计算每一个元素距离最近0元素的距离。

注意：

1. 给定矩阵元素个数不超过10,000
2. 给定矩阵中至少包含1个0元素
3. 相邻单元格是指上、下、左、右四个方向

解题思路：

队列（Queue）

初始令step = 0，将matrix中所有1元素加入队列queue

循环，直到queue为空：

  令step = step + 1

  遍历queue中的元素，记当前元素为p，坐标为(x, y)：

    若p的相邻元素中包含0元素，则p的距离设为step，从queue中移除p
    
  将上一步中移除的元素对应的matrix值设为0

上述过程可以类比拓扑排序。

Python代码：

class Solution(object):
    def updateMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        h, w = len(matrix), len(matrix[0])
        ans = [[0] * w for x in range(h)]
        queue = [(x, y) for x in range(h) for y in range(w) if matrix[x][y]]
        step = 0
        while queue:
            step += 1
            nqueue, mqueue = [], []
            for x, y in queue:
                zero = 0
                for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] == 0:
                        zero += 1
                if zero:
                    ans[x][y] = step
                    mqueue.append((x, y))
                else: 
                    nqueue.append((x, y))
            for x, y in mqueue:
                matrix[x][y] = 0
            queue = nqueue
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/03/19/leetcode-01-matrix/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码