type
status
slug
summary
tags
category
icon
password
new update day
Property
Oct 22, 2023 01:31 PM
created days
Last edited time
Oct 22, 2023 01:31 PM

542. 01 矩阵

题目描述

notion image

思路

对于矩阵中的每一个元素，如果它的值为 0，那么离它最近的 0 就是它自己。如果它的值为 1那么我们就需要找出离它最近的 0，并且返回这个距离值。那么我们如何对于矩阵中的每一个 1，都快速地找到离它最近的 0 呢?
我们不妨从一个简化版本的问题开始考虑起。假设这个矩阵中恰好只有一个 0，我们应该怎么做? 由于矩阵中只有一个 0，那么对于每一个 1，离它最近的 0 就是那个唯一的 0。如何求出这个距离呢?我们可以想到两种做法:
  • 如果 0 在矩阵中的位置是，1 在短阵中的位置是，那么我们可以直接算出 0 和 1之间的距离。因为我们从 1 到 0 需要在水平方向走 步，竖直方向走 步，那么它们之间的距离就为 + ;
  • 我们可以从 0 的位置开始进行 广度优先搜索。广度优先搜索可以找到从起点到其余所有点的 最短距离，因此如果我们从 0 开始搜索，每次搜索到一个 1，就可以得到 0 到这个1 的最短距离，也就离这个 1 最近的 0的距离了 (因为矩阵中只有一个 0)。
举个例子，如果我们的矩阵为：
其中只有一个 0，剩余的 1 我们用短横线表示。如果我们从 0 开始进行广度优先搜索那么结果依次为:

算法解答

参考资料

力扣
力扣
https://leetcode.cn/problems/01-matrix/solutions/202012/01ju-zhen-by-leetcode-solution/
相关文章
116. 填充每个节点的下一个右侧节点指针
Leetcode Problem: 3. 无重复字符的最长子串
116. 填充每个节点的下一个右侧节点指针Build ollvm yourself