[LeetCode]01 Matrix

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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