腐烂橘子问题详解：如何计算感染所有橘子所需的最小时间

在算法学习和面试准备的过程中，图论问题总是让人既兴奋又头疼。今天，我们不仅要解决一个经典的图遍历问题，还要深入探讨其中的优化策略。我们将一起研究“腐烂橘子”问题：在一个网格中，给定新鲜橘子、腐烂橘子和空单元格，计算出所有新鲜橘子腐烂所需的最小时间。如果无法让所有橘子腐烂，我们还需要能够识别这种情况。

在这篇文章中，我们将通过三个不同的维度来剖析这个问题：首先，我们会通过简单的迭代来模拟传染过程；其次，我们会尝试使用广度优先搜索（BFS）来达到最优的时间复杂度；最后，我们还会讨论一些边界情况和实际应用场景。准备好了吗？让我们开始这次算法之旅吧。

问题理解与核心逻辑

首先，让我们明确一下问题的规则，这对于构建解决方案至关重要。我们有一个 INLINECODEe1d54333 的矩阵 INLINECODEbdbe297a，其中的数值代表三种状态：

• 0：空单元格（墙壁），橘子无法穿过，腐烂也不会通过这里传播。
• 1：新鲜橘子，这是我们要被“感染”的目标。
• 2：腐烂橘子，这是感染源。

传播规则： 每一个腐烂橘子（值为 2）在每一分钟内，都会使其上下左右相邻（4连通）的新鲜橘子（值为 1）变成腐烂橘子。我们需要计算的是，直到再也没有新鲜橘子存在时，经过了多少分钟。

这个问题本质上是一个多源广度优先搜索问题。你可以把所有的初始腐烂橘子看作是图中的多个“起点”，它们同时向外扩散，寻找“终点”（新鲜橘子）。扩散的距离（层数）就是我们所需的时间。

方法一：朴素模拟法

让我们先从最直观的方法开始。正如我们在日常思维中模拟的那样，我们让时间一秒一秒地流逝，每一秒我们检查整个网格，看看哪些橘子在这一秒被腐烂了。

算法思路：

• 我们维护一个计时器 elapsedTime，初始为 0。
• 我们遍历整个矩阵。如果在第 INLINECODEc40bfcfd 分钟，某个单元格的值是 INLINECODE8535805a（例如初始腐烂橘子是 2，即 0+2），那么它在这一分钟具有传染性。
• 当我们找到具有传染性的橘子时，我们检查它的四个邻居。如果邻居是新鲜的（值为 1），我们将邻居的值更新为 mat[i][j] + 1（即变成下一分钟的腐烂源）。这种标记法非常巧妙，它不仅标记了橘子已腐烂，还记录了它是在哪一分钟被腐烂的，从而防止了它在同一分钟内进行二次传播。
• 如果在某次遍历中，没有任何新鲜橘子被腐烂，说明扩散停止，我们可以退出循环。
• 最后，再次检查网格。如果还有值为 1 的橘子，说明存在无法被感染的区域，返回 -1；否则，返回 elapsedTime。

虽然这个方法逻辑清晰，但它的时间复杂度较高。在最坏情况下，我们可能需要遍历整个网格多次，复杂度达到了 O((n x m)^2)。

#### C++ 实现：朴素迭代法

#include 
#include 
using namespace std;

// 辅助函数：判断坐标是否安全
bool isSafe(int i, int j, int n, int m) {
    // 确保不越界
    return 0 <= i && i < n && 0 <= j && j < m;
}

int orangesRot(vector<vector>& mat) {
    int n = mat.size();
    int m = mat[0].size();

    // 标记位：用于检查在一次迭代中是否发生了腐烂
    bool changed;
    // 经过时间的计数器
    int elapsedTime = 0;

    // 四个方向：下、右、上、左
    vector<vector> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    // 持续迭代直到没有新的腐烂发生
    while (true) {
        changed = false;
        // 遍历每一个单元格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                
                // 关键逻辑：如果该橘子是在 elapsedTime 时刻腐烂的（值为 elapsedTime + 2）
                // 它将在当前这一轮（代表这一分钟）进行感染
                if (mat[i][j] == elapsedTime + 2) {
                    
                    // 检查四个方向的邻居
                    for (auto& dir : directions) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        
                        // 如果邻居安全且是新鲜橘子（值为1）
                        if (isSafe(x, y, n, m) && mat[x][y] == 1) {
                            // 将其腐烂，并标记时间戳
                            // 例如：elapsedTime=0时，初始2感染1，使其变为3
                            // 这意味着它在t=1时具有传染性
                            mat[x][y] = mat[i][j] + 1; 
                            changed = true;
                        }
                    }
                }
            }
        }
        
        // 如果没有任何橘子被腐烂，说明传染结束
        if (!changed) break;
        
        // 时间增加
        elapsedTime++;
    }

    // 最终检查：是否还有新鲜橘子残留？
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 1) {
                return -1; // 无法全部腐烂
            }
        }
    }

    return elapsedTime;
}

// Driver Code
int main() {
    vector<vector> mat = {
        {2, 1, 0, 2, 1}, 
        {1, 0, 1, 2, 1}, 
        {1, 0, 0, 2, 1}
    };
    cout << "Minimum time to rot: " << orangesRot(mat) << endl;
    return 0;
}

方法二：广度优先搜索（BFS）—— 期望的高效解法

你可能会觉得上面的方法有点“笨”，因为它每秒钟都要重新扫描整个网格。有没有一种方法，能够精确地控制每一分钟只处理当前被腐烂的那一批橘子呢？答案是肯定的，那就是使用队列实现的广度优先搜索。

BFS 是处理此类“层级扩散”问题的利器。想象一下，所有初始的腐烂橘子是“第一波”感染源。它们同时向外扩散，感染到的橘子组成“第二波”，以此类推。

优化思路：

• 初始化阶段：首先遍历一次矩阵。将所有初始状态为腐烂橘子（2）的坐标加入队列。同时，统计新鲜橘子（1）的总数。如果队列是空的但仍有新鲜橘子，直接返回 -1；如果没有新鲜橘子，直接返回 0。

n2. 处理阶段：我们开始处理队列中的元素。这里有一个技巧：我们可以使用 INLINECODE55c09df8 循环，但在内部增加一个基于当前队列长度的 INLINECODEafb1be53 循环。这能让我们区分“当前分钟”和“下一分钟”的橘子。

• 时间推进：每当我们处理完当前队列中的所有元素（即当前波次的所有腐烂源都完成了感染工作），我们就将时间 +1。如果在这一分钟内有新鲜橘子被腐烂并加入了队列，它们将在下一轮被处理。
• 终止条件：当队列为空时，说明没有新的感染源了。此时检查新鲜橘子计数是否为 0。

这种方法的时间复杂度是 O(n x m)，因为我们每个单元格最多被访问一次（入队一次）。这是解决此问题的最优时间复杂度。

#### C++ 实现：广度优先搜索

#include 
#include 
#include 
using namespace std;

// 定义坐标结构体，方便操作
struct Coordinate {
    int r, c;
    Coordinate(int r, int c) : r(r), c(c) {}
};

int orangesRottingBFS(vector<vector>& mat) {
    int n = mat.size();
    int m = mat[0].size();
    queue q;
    int fresh = 0; // 新鲜橘子计数器

    // 1. 初始化队列
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 2) {
                // 将所有初始腐烂橘子入队
                q.push(Coordinate(i, j));
            } else if (mat[i][j] == 1) {
                // 统计新鲜橘子数量
                fresh++;
            }
        }
    }
    
    // 如果没有新鲜橘子，不需要时间
    if (fresh == 0) return 0;
    
    // 如果有新鲜橘子但没有腐烂橘子，不可能完成，返回 -1
    if (q.empty()) return -1;

    int time = 0;
    // 四个方向数组
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // 2. 开始 BFS
    while (!q.empty()) {
        // 关键：记录当前层的节点数量
        // 这代表当前这一分钟内有多少个橘子在同时进行感染
        int size = q.size();
        bool rottedAny = false;

        for (int i = 0; i < size; i++) {
            Coordinate curr = q.front();
            q.pop();

            // 检查四个方向
            for (int k = 0; k = 0 && nr = 0 && nc < m && mat[nr][nc] == 1) {
                    // 腐烂它
                    mat[nr][nc] = 2;
                    fresh--; // 减少新鲜橘子数量
                    rottedAny = true;
                    // 将新腐烂的橘子加入队列，作为下一波的感染源
                    q.push(Coordinate(nr, nc));
                }
            }
        }

        // 只有在当前层确实腐烂了橘子的情况下，时间才增加
        if (rottedAny) {
            time++;
        }
    }

    // 3. 最终检查
    // 如果新鲜橘子数量为0，说明全部腐烂，返回累计时间
    // 否则，说明有无法到达的橘子，返回 -1
    return fresh == 0 ? time : -1;
}

int main() {
    vector<vector> mat = {
        {2, 1, 0, 2, 1}, 
        {0, 0, 1, 2, 1}, 
        {1, 0, 0, 2, 1}
    };
    int result = orangesRottingBFS(mat);
    if (result != -1)
        cout << "Minimum time to rot: " << result << endl;
    else 
        cout << "All oranges cannot rot." << endl;
    return 0;
}

#### Python 实现：同样的逻辑，更简洁的语法

为了让你更好地理解，我们也提供一个 Python 的版本。Python 的 collections.deque 是实现 BFS 队列的最佳选择，因为它的 pop(0) 操作是 O(1) 的。

from collections import deque

def orangesRottingBFS(mat):
    if not mat: return 0
    
    rows, cols = len(mat), len(mat[0])
    queue = deque()
    fresh_count = 0
    
    # 初始化：统计新鲜橘子，并将腐烂橘子入队
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 2:
                queue.append((r, c))
            elif mat[r][c] == 1:
                fresh_count += 1
                
    # 如果没有新鲜橘子，直接返回0
    if fresh_count == 0:
        return 0
    
    # 四个方向
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    time = 0
    
    while queue and fresh_count > 0:
        # 每次处理当前层的所有节点
        for _ in range(len(queue)):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # 如果是新鲜橘子
                if 0 <= nr < rows and 0 <= nc  0，说明进入了下一分钟
        if queue:
            time += 1
            
    return time if fresh_count == 0 else -1

# 测试
mat = [[2,1,0,2,1], [1,0,1,2,1], [1,0,0,2,1]]
print(f"Minimum time: {orangesRottingBFS(mat)}")

常见陷阱与调试技巧

在实际编码中，你可能会遇到一些棘手的情况。让我们来看看如何处理它们：

• 孤立的新鲜橘子：

场景*：有些新鲜橘子被 0（空单元格）完全包围，没有任何腐烂橘子能接触到它们。
解决方案*：这就是为什么我们在 BFS 结束后（或每次迭代后）必须检查 INLINECODEe87e48e7 或遍历矩阵查找残留的 INLINECODE17f7f368。如果存在这样的橘子，必须返回 -1。

• 时间计数偏差：

场景*：在 BFS 中，什么时候让 time 加 1 很容易出错。如果你在每次循环加 1，可能会多算。
解决方案*：按照我们上面的代码，处理完“当前这一层”的所有节点后，再加 1。因为“当前这一层”是同时发生的，只代表过了 1 单位时间。或者记录橘子变成腐烂时的值 dist[nr][nc] = dist[r][c] + 1，最后取矩阵中的最大值减 2。

• 空网格或无橘子网格：

场景*：输入是 INLINECODE1d448a3e 或者全是 INLINECODEb711778a。
解决方案*：在代码开头做防御性检查，避免数组越界或无意义的计算。

实际应用场景

虽然这听起来像是一个抽象的数学谜题，但这种算法模型在现实世界中有着广泛的应用：

• 网络病毒传播模拟：计算一个计算机病毒在局域网中感染所有设备所需的时间。这里的橘子就是设备，腐烂就是感染。
• 图像处理：在某些图像分割算法中，从种子点开始填充区域，计算填充到整个连通域所需的步长。
• 游戏开发：计算游戏中毒素或法力光环的扩散范围和持续时间。

总结与关键要点

我们深入探讨了腐烂橘子问题，从简单的迭代模拟到高效的广度优先搜索。通过对比我们可以看到，虽然朴素方法容易想到，但在处理大规模数据时效率低下。BFS 利用队列的先进先出特性，完美地模拟了并行传染的过程，将时间复杂度优化到了 O(n x m)。

核心记忆点：

• 这是一个多源 BFS 问题。
• 初始化时将所有“起始点”入队。
• 使用“层级遍历”的概念来控制时间的流逝（处理完一层节点，时间+1）。
• 最后一定要检查是否还有剩余的“新鲜”节点。

下次遇到类似的网格扩散问题，你可以自信地拿出这套 BFS 模板来解决了！希望这篇文章能帮助你更好地理解图论算法的魅力。继续练习，保持好奇！