LeetCode 994. 腐烂的橘子 题目描述 在给定的一个 m x n 网格中，每个单元格可以有以下三个值之一： 值 0 代表一个空单元格； 值 1 代表一个新鲜橘子； 值 2 代表一个腐烂的橘子。 每分钟，任何与腐烂的橘子（在四个正方向上，即上、下、左、右）相邻的新鲜橘子都会变成腐烂的橘子。你需要计算直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，则返回 -1 。 解题过程 这个问题可以看作是一个多源点的广度优先搜索（BFS）问题。腐烂的橘子就像是“感染源”，每分钟会向四周扩散。BFS非常适合这种逐层扩散的场景，因为它可以确保我们首先处理完当前分钟所有可能被感染的橘子，然后再进入下一分钟。 问题分析与思路形成 目标 ：计算所有新鲜橘子被腐烂所需的时间（分钟数）。 核心观察 ：腐烂的过程是同时从多个点（初始所有腐烂的橘子）开始，并逐分钟（逐层）向外传播的。这完美契合了BFS“一层一层”遍历的特性。 关键点 ： 多源点BFS ：我们不是从一个点开始，而是从网格中所有初始状态就是腐烂的橘子（值为2的单元格）开始进行BFS。 队列初始化 ：在开始BFS之前，我们需要把所有这些“源头”都加入到队列中。 时间记录 ：我们需要记录BFS的层数，这个层数就对应着经过的分钟数。当BFS无法再继续（即队列为空）时，我们需要检查是否还有新鲜橘子残留。 详细步骤 步骤一：初始化 创建一个队列（通常用 queue ），用于BFS遍历。 遍历整个网格，统计新鲜橘子的数量（值为 1 的单元格个数），我们记为 fresh_count 。 在遍历网格的同时，将所有腐烂橘子（值为 2 的单元格）的坐标 (i, j) 加入队列。这些是我们的BFS起点。 步骤二：特殊情况处理 如果初始的新鲜橘子数量 fresh_count 为0，意味着网格里一开始就没有好橘子，那么所需时间就是0分钟。 步骤三：开始BFS（模拟腐烂过程） 初始化时间变量 minutes = 0 。 当队列不为空 并且 还有新鲜橘子（ fresh_count > 0 ）时，开始循环。这个循环的每一轮，对应着“一分钟”的流逝。 在每一分钟开始时，记录当前队列的大小 size 。这个 size 代表了在当前这一分钟开始时，所有“处于腐烂状态且即将去感染邻居”的橘子的数量。 然后，我们进行一个内层循环，次数为 size 。在这个内层循环中，我们依次从队列中取出一个腐烂橘子的坐标 (i, j) 。 检查这个腐烂橘子的四个方向（上、下、左、右）的相邻单元格 (ni, nj) ： 如果 (ni, nj) 在网格范围内，并且该单元格是新鲜橘子（值为 1 ）。 那么，我们进行以下操作： 将这个新鲜橘子标记为腐烂（将网格中 grid[ni][nj] 的值从 1 改为 2 ）。 将新的腐烂橘子 (ni, nj) 加入队列，它将在下一分钟去感染它的邻居。 将新鲜橘子的计数 fresh_count 减1。 当内层循环（处理完当前分钟的所有腐烂橘子）结束后，一分钟就过去了。但是， 只有在确实有新的橘子被腐烂（即 fresh_count 减少了）的情况下，我们才将时间 minutes 加1 。这是因为有可能在某一分钟，队列里虽然有橘子，但它们周围已经没有好橘子了，这一分钟实际上没有发生新的感染。 步骤四：返回结果 BFS结束后，我们检查新鲜橘子的数量 fresh_count 。 如果 fresh_count 等于0，说明所有橘子都腐烂了，返回经过的分钟数 minutes 。 如果 fresh_count 大于0，说明有些新鲜橘子无法被腐烂到（比如被空单元格隔离了），返回 -1 。 总结 这个算法的核心是利用多源点BFS来模拟腐烂的扩散。通过队列来管理待处理的腐烂橘子，并通过记录队列的初始大小来精确控制“分钟”这个时间单位。最后，通过检查是否还有剩余的新鲜橘子来判断是否所有橘子都能被腐烂。算法的时间复杂度是 O(m * n)，因为每个单元格最多入队一次。