题目

难度：★★☆☆☆
类型：数组
方法：二分法

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例

示例 1:

输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0

示例 2:

输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1
注意:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解答

对于二维矩阵有关的，并且与位置关系有关的，我们可以考虑用淹没的办法解决：

把所有零在的位置看做海洋，1在的位置看做陆地，并且越靠近内陆地区，山脉越高，坡度在任何地方都是完全均匀的，求陆地的等高线图。

我们逐渐的升高海平面，一层一层的淹没陆地，每淹没一层，记录下淹没的陆地区域，直到将整个陆地淹没。

class ZeroOneMatrix:
    def __init__(self, matrix):
        # self.matrix = matrix
        self.height = len(matrix)
        self.width = len(matrix[0])
        self.contour_map = [[0 if matrix[h][w] == 0 else None for w in range(self.width)] for h in range(self.height)]
        # self.ocean = [[0 if matrix[h][w] == 0 else None for w in range(self.width)] for h in range(self.height)]

    def is_valid(self, h, w):
        return 0 <= h < self.height and 0 <= w < self.width

    def submerge_around(self, h, w):
        nums = 0
        neighbors = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
        for nh, nw in neighbors:
            if self.is_valid(nh, nw) and self.contour_map[nh][nw] is None:
                self.contour_map[nh][nw] = self.contour_map[h][w] + 1
                nums += 1
        return nums

    def submerge(self):
        while True:
            current_ocean = [(h, w) for h in range(self.height) for w in range(self.width) if self.contour_map[h][w] is not None]
            total = sum([self.submerge_around(h, w) for h, w in current_ocean])
            if total == 0:
                break


class Solution:
    def updateMatrix(self, matrix):
        matrix = ZeroOneMatrix(matrix=matrix)
        matrix.submerge()
        return matrix.contour_map

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析