手记

LeetCode 542. 01 矩阵

542. 01 矩阵

题目


给定一个由 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。
  • 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解题思路


思路:广度优先搜索

可以从 0 的位置开始进行广度优先搜索。

将 0 视为源点,将其都入队,各个 0 向 1 扩散(在这里每个 1 都是被离它最近的 0 扩散到的)。

扩散的时候要注意,在返回的矩阵中,可以在对应的坐标中设置距离值,同时标记是否访问过。需要注意的是其中 0 元素距离为 0,在构建返回矩阵时,设默认初始值为 0,这个时候,可以直接将源点 0 放入已标记部分。

具体看下面代码实现。

代码实现


class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])

        # 构建返回矩阵
        ans = [[0] * n for _ in range(m)]
        # 先找所有源点 0 的位置
        zero = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
        # 将所有源点 0 入队列
        from collections import deque
        queue = deque(zero)
        # 标记
        # 这里将源点 0 的位置加入标记
        # 是因为源点 0 的距离就是 0
        # 可不做变化,返回矩阵默认初始值为 0
        sign = set(queue)

        # 需扩散的四个方位
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            # 出队列,进行扩散
            i, j = queue.popleft()
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0<=ni<m and 0<=nj<n and (ni, nj) not in sign:
                    ans[ni][nj] = ans[i][j] + 1
                    queue.append((ni, nj))
                    sign.add((ni, nj))

        return ans

实现结果



以上就是使用广度优先搜索的方法,找出源点 0 的位置进行扩散,进而解决《542. 01 矩阵》的主要内容,需要注意的是扩散的同时,需要标记哪部分已经扩散到的。


1人推荐
随时随地看视频
慕课网APP