542. 01 矩阵
给定一个由
0和1组成的矩阵mat，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离。
两个相邻元素间的距离为 1。
示例一：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例二：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
解题方法：多源广度优先搜索
class Solution {
func updateMatrix(_ mat: [[Int]]) -> [[Int]] {
let dRow = [1, -1, 0, 0]
let dCol = [0, 0, 1, -1]
let rowCount = mat.count
let colCount = mat[0].count
var result = mat
var seen = [Int: Bool]()
var queue = [Int]()
for row in 0..<rowCount {
for col in 0..<colCount {
if mat[row][col] == 0 {
let code = row * colCount + col
queue.append(code)
seen[code] = true
}
}
}
while !queue.isEmpty {
let code = queue.removeFirst()
let row = code / colCount
let col = code % colCount
for i in 0..<4 {
let newRow = row + dRow[i]
let newCol = col + dCol[i]
let newCode = newRow * colCount + newCol
if newRow >= 0 && newRow < rowCount && newCol >= 0 && newCol < colCount && !seen[newCode, default: false] {
result[newRow][newCol] = result[row][col] + 1
queue.append(newCode)
seen[newCode] = true
}
}
}
return result
}
}
解题思路
对于矩阵中的每一个元素，如果它的值为 0，那么离它最近的 0 就是它自己。如果它的值为 1，那么我们就需要找出离它最近的 0，并且返回这个距离值。那么我们如何对于矩阵中的每一个 1，都快速地找到离它最近的 0 呢？
我们不妨从一个简化版本的问题开始考虑起。假设这个矩阵中恰好只有一个 0，我们应该怎么做？由于矩阵中只有一个 0，那么对于每一个 1，离它最近的 0 就是那个唯一的 0。如何求出这个距离呢？ - 我们可以从 0 的位置开始进行 广度优先搜索。广度优先搜索可以找到从起点到其余所有点的 最短距离，因此如果我们从 0 开始搜索，每次搜索到一个 1，就可以得到 0 到这个 1 的最短距离，也就离这个 1 最近的 0 的距离了（因为矩阵中只有一个 0）。
我们在进行广度优先搜索的时候会使用到队列，在只有一个 0 的时候，我们在搜索前会把这个 0 的位置加入队列，才能开始进行搜索；如果有多个 0，我们只需要把这些 0 的位置都加入队列就行了。
这样做为什么是正确的呢？ - 我们需要对于每一个 1 找到离它最近的 0。如果只有一个 0 的话，我们从这个 0 开始广度优先搜索就可以完成任务了； - 但在实际的题目中，我们会有不止一个 0。我们会想，要是我们可以把这些 0 看成一个整体好了。有了这样的想法，我们可以添加一个「超级零」，它与矩阵中所有的 0 相连，这样的话，任意一个 1 到它最近的 0 的距离，会等于这个 1 到「超级零」的距离减去一。由于我们只有一个「超级零」，我们就以它为起点进行广度优先搜索。这个「超级零」只和矩阵中的 0 相连，所以在广度优先搜索的第一步中，「超级零」会被弹出队列，而所有的 0 会被加入队列，它们到「超级零」的距离为 1。这就等价于：一开始我们就将所有的 0 加入队列，它们的初始距离为 0。这样以来，在广度优先搜索的过程中，我们每遇到一个 1，就得到了它到「超级零」的距离减去一，也就是 这个 1 到最近的 0 的距离。
复杂度分析
- 时间复杂度：
O(R x C)，其中R为矩阵行数，C为矩阵列数，即矩阵元素个数。广度优先搜索中每个位置最多只会被加入队列一次，因此只需要O(R x C)的时间复杂度。 - 空间复杂度：
O(R x C)，其中R为矩阵行数，C为矩阵列数，即矩阵元素个数。除答案数组外，最坏情况下矩阵里所有元素都为0，全部被加入队列中，此时需要O(R x C)的空间复杂度。