Rotten Oranges Problem in Java

矩阵遍历是计算问题解决中的一个常见问题，与路径查找、模拟和游戏有关。网上讨论的一个此类问题是腐烂橙子问题，它模拟了橙子网格上的腐烂传播。这是 BFS 的理论性能和实际实现，以及图遍历算法的应用。

问题陈述

该问题可以定义如下：

您将获得一个二维网格，其中：

• 0 表示空单元格。
• 1 表示新鲜橙子。
• 2 表示腐烂的橙子。

每分钟，任何腐烂的橙子都会导致其相邻的新鲜橙子腐烂，包括它上面的、下面的、左边的和右边的。

您的目标是找到所有橙子都腐烂的最小时间。如果任何新鲜橙子超出范围，则应返回 -1。

示例

• 首先，左上角的橙子是坏的。
• 一分钟内，它会腐蚀旁边的新鲜橙子。
• 2 分钟后，传播开始，4 分钟后所有橙子都腐烂了。

方法

这是一个基于广度优先搜索 (BFS) 的解决方案，通常用于图中的层序遍历。BFS 在这里很有用的三个原因：腐烂是逐层传播的，BFS 也是逐层访问图中的节点。

解决问题的步骤

初始化：遍历网格以

• 计算所有新鲜橙子。
• 将所有腐烂橙子的位置推入队列，因为这些将是 BFS 的起始点。

广度优先搜索

• 取消一个腐烂的橙子，并检查它周围的四个单元格：上、下、左、右。
• 否则，如果相邻单元格是新鲜橙子，则将其变为腐烂橙子，增加腐烂橙子计数器，并将其位置添加到队列中。

时间跟踪：在 BFS 遍历期间，跟踪分钟数。

完成检查

• 如果 BFS 遍历后没有剩余的新鲜橙子，则返回所测得的时间。
• 如果还有一些新鲜橙子留下，则返回 -1。

文件名：RottenOranges.java

输出

 
Minimum time to rot all oranges: 4   

复杂度分析

时间复杂度

BFS 遍历的过程意味着算法中的每个单元格最多只处理一次。

此解决方案的时间复杂度为 O(N×M)，因为它在这些算法中发挥了最大作用。

空间复杂度

需要为队列分配空间，在最坏情况下，它可能包含多达 O(N×M) 个元素。

结论

腐烂橙子问题是一个很好的例子，可以展示 BFS 的代表性应用，包括污染传播（如感染）、野火建模和各种扩散集。

以这种方式旋转相邻单元格并跟踪时间也可以同时保证效率和准确性。在 Java 中，这样做可以巩固图的基本概念以及如何使用队列来处理图。

这个问题还包括一些棘手的情况，例如，如果没有新鲜橙子，或者某些新鲜橙子无法到达。这是因为它除了在算法爱好者热衷于解决它之外，还有实际用途。