C++ 中的烂橙子问题

引言

烂橘子问题 是一个经典的算法问题，它考察我们对图遍历算法，特别是广度优先搜索 (BFS) 的理解。它经常出现在面试中，涉及多源 BFS 和网格问题解决等概念。

本文将通过首先解释如何解决这个问题，然后逐步讲解如何在 C++ 中实现它来解决这个问题。

问题陈述

我们给定一个二维 数组 网格，其中每个单元格可以有以下三个值之一：0 表示空单元格，1 表示新鲜橘子，2 表示腐烂橘子。

如果一个新鲜橘子至少有一个相邻（上、下、左、右）的腐烂橘子，那么经过一个单位时间后它就会腐烂。目标是确定腐烂网格中所有新鲜橘子所需的最小时间。如果无法腐烂所有新鲜橘子，则返回 -1。

约束

• 网格的维度是 m x n。
• 每个单元格的值在 0 到 2 之间。

方法

多源广度优先搜索是解决此问题的好方法，因为腐烂过程是由于多个来源（腐烂的橘子）同时传播的。以下是其工作原理的细分

1. 设置一个网格，并查找所有腐烂橘子的坐标并将其入队。
2. 以类似的方式，继续进行 BFS，同时使用队列腐烂剩余的相邻橘子，每腐烂一个橘子，就减少新鲜橘子的计数。
3. 返回所有新鲜橘子腐烂所需的时间，如果有一些新鲜橘子未被触及，则返回 -1。

示例 1

让我们举一个例子来说明 C++ 中的烂橘子问题。

输出

Minimum time required to rot all oranges: 4   

代码解释

1. 输入遍历： 在网格的第一次遍历过程中，识别腐烂和新鲜的橘子并标记它们的位置。
2. BFS 循环： 每次执行 BFS 循环时，都会处理队列的一个级别，该级别代表一个时间单位。
3. 边界和新鲜检查： 在腐烂橘子之前，代码确保单元格在边界内并包含新鲜橘子。
4. 结果： 如果没有新鲜橘子剩下，则返回整个时间区域，否则返回 -1。

时间和空间复杂度

• 时间复杂度： O(m×n)，其中 m 和 n 是网格的维度。每个单元格都独立处理一次。
• 空间复杂度： O(m×n) 指 BFS 算法中队列占用的空间。

示例 2

让我们再举一个例子来说明 C++ 中的烂橘子问题。

输出

Input Grid:
2 1 1 0 
1 1 0 2 
0 1 1 1 
2 0 0 1 

Minimum time required to rot all oranges: 4

Final Grid State:
2 2 2 0 
2 2 0 2 
0 2 2 2 
2 0 0 2   

说明

1. validateGrid： 此过程很重要，因为它确保网格有效（不为空，仅包含 0、1、2）。无效网格会引发错误。
2. printGrid： 它用于通过打印网格进行调试或可视化。
3. minimumTimeToRot
   • 初始化： 它计算新鲜橘子，同时将所有腐烂的橘子入队。
   • BFS 遍历： 腐烂沿着所有四个方向传播（这就是为什么有队列）。每一步都记录时间，每当一个新鲜橘子被吃掉时，时间就会递减。
   • 结果： 如果所有橘子都腐烂了，则返回总时间。如果仍然有新鲜橘子，则返回 -1。
4. main： 设置输入网格，验证它，计算结果并打印网格的初始/最终状态以及输出。

复杂度分析

• 时间复杂度： O(m×n)
• 空间复杂度： BFS 中使用的队列为 O(m×n)。

要点

1. 多源 BFS 解释
   在这里，我们可以看到多源 BFS 的实际应用，所有来源（腐烂的橘子）同时积极传播。
2. 网格遍历技术
   它演示了如何使用有效的方向向量（上、下、左、右）遍历二维网格。
3. 边缘情况处理
   • 没有新鲜橘子的网格（输出 0）。
   • 只能隔离且不会腐烂的新鲜橘子（输出 -1）。
   • 空网格或没有有效输入的网格。
4. BFS 队列
   它确保在跳转到下一个时间级别之前处理同一“时间级别”的所有节点（橘子）。
5. 实际用例
   模拟现实生活中的问题，如疾病传播、火灾蔓延模拟，甚至资源扩散。

结论

总之，烂橘子问题 是一个练习 BFS 和空间网格问题的完美问题。它强调了多源 BFS 的原理，并允许我们将现实生活场景与图遍历中的概念联系起来。