994. 腐烂的橘子
在给定的网格中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回
-1。
示例一：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例二：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
解题方法：多源广度优先搜索
class Solution {
func orangesRotting(_ grid: [[Int]]) -> Int {
let dRow = [0, 0, 1, -1]
let dCol = [1, -1, 0, 0]
let rowCount = grid.count
let colCount = grid[0].count
var grid = grid
var queue = [Int]()
var distance = [Int: Int]()
var freshCount = 0
for row in 0..<grid.count {
for col in 0..<grid[0].count {
if grid[row][col] == 2 {
let code = row * colCount + col
queue.append(code)
distance[code] = 0
} else if grid[row][col] == 1 {
freshCount += 1
}
}
}
var ans = 0
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]
if newRow >= 0 && newRow < grid.count && newCol >= 0 && newCol < grid[0].count && grid[newRow][newCol] == 1 {
freshCount -= 1
grid[newRow][newCol] = 2
let newCode = newRow * colCount + newCol
queue.append(newCode)
distance[newCode] = distance[code]! + 1
ans = distance[newCode]!
}
}
}
if freshCount > 0 {
return -1
}
return ans
}
}
解题思路
观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。
假设这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂，而这个腐烂橘子刚开始在的时间是 −1 ，那么按照广度优先搜索的算法，下一分钟也就是第 0 分钟的时候，这个腐烂橘子会把它们都变成腐烂橘子，然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，最后每个新鲜橘子被腐烂的最短时间 distance 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。
为了确认是否所有新鲜橘子都被腐烂，可以记录一个变量 freshCount 表示当前网格中的新鲜橘子数，广度优先搜索的时候如果有新鲜橘子被腐烂，则 freshCount -= 1，最后搜索结束时如果 freshCount 大于 0 ，说明有新鲜橘子没被腐烂，返回 −1 ，否则返回所有新鲜橘子被腐烂的时间的最大值即可。
复杂度分析
- 时间复杂度：
O(R x C)，其中R为矩阵行数，C为矩阵列数，即矩阵元素个数。即进行一次广度优先搜索的时间。 - 空间复杂度：
O(R x C)，其中R为矩阵行数，C为矩阵列数，即矩阵元素个数。需要额外的distance散列表来记录每个橘子被腐烂的最短时间，大小为O(R x C)，且广度优先搜索中队列里存放的状态最多不会超过R x C个，最多需要O(R x C)的空间，所以最后的空间复杂度为O(R x C)。