NOI 竞赛模拟题：腐烂的橘子

题目描述

在一个 $m \times n$ 的网格 grid 中，每个单元格可能包含以下三种值之一：

• 0 代表空单元格；
• 1 代表新鲜橘子；
• 2 代表腐烂的橘子。

每分钟，腐烂的橘子都会与其**相邻（上下左右 4 个方向）**的新鲜橘子发生接触，使这些新鲜橘子也变成腐烂状态。

请你计算并输出：直到单元格中没有新鲜橘子为止所需要的最少分钟数。如果不可能完成，则输出 -1。

---

输入格式

第一行包含两个整数 $m$ 和 $n$，表示矩阵的行数和列数。 接下来 $m$ 行，每行包含 $n$ 个以空格分隔的整数（0, 1 或 2）。

输出格式

输出一个整数，表示最少分钟数。如果最后仍有新鲜橘子，输出 -1。

---

输入输出样例

样例 1

输入：

3 3
2 1 1
1 1 0
0 1 1

输出：

4

样例 2

输入：

3 3
2 1 1
0 1 1
1 0 1

输出：

-1

样例 3

输入：

1 2
0 2

输出：

0

数据范围与提示

• $m = grid.length$
• $n = grid[i].length$
• $1 \le m, n \le 10$
• $grid[i][j]$ 仅为 0, 1 或 2

---

1. 预备知识点

• 多源广度优先搜索 (Multi-source BFS)：与单源 BFS 不同，本题初始状态可能有多个腐烂橘子，它们同时开始向外扩散。
• 状态同步更新：BFS 的“层级”概念天然对应题目中的“时间（分钟）”。
• 计数器技巧：在搜索前统计新鲜橘子的总数，可以更高效地判断是否全部腐烂。

---

2. 启发式思路引导

第一步：找出“传染源”

在草稿纸上画一个网格。如果此时有 3 个腐烂的橘子，它们是同时开始传染周围的。

• 思考：这和从一个点出发的最短路有什么区别？
• 结论：我们需要在初始化队列时，将所有初始值为 2 的坐标全部入队。这就是“多源 BFS”。

第二步：定义“时间步”

• 每一层 BFS 扩散代表 1 分钟。
• 当队列中第一批橘子传染完其邻居后，时间加 1。
• 注意：如果某分钟没有传染任何新的橘子，时间不应增加。

第三步：判断终局

• 什么时候输出 -1？当队列空了，但地图上还残留有值为 1 的新鲜橘子时。
• 优化建议：在初始化时记录新鲜橘子的总数 fresh_count。每传染一个，fresh_count--。最后只需判断 fresh_count 是否为 0。

第四步：复杂度分析

• 时间复杂度：每个单元格最多入队一次，总时间 $O(M \times N)$。
• 空间复杂度：需要队列存储坐标，最坏情况下（全是腐烂橘子）空间为 $O(M \times N)$。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 统计新鲜橘子数 fresh 且记录所有腐烂橘子坐标到 Q"] --> B{"fresh 等于 0?"}
    B -- "是" --> C["输出 0, 结束"]
    B -- "否" --> D["初始化分钟数 minutes 为 0"]
    D --> E{"Q 是否为空 且 fresh 大于 0?"}
    E -- "否" --> F{"fresh 等于 0?"}
    F -- "是" --> G["输出 minutes"]
    F -- "否" --> H["输出 -1"]
    E -- "输入队列不为空" --> I["获取当前队列长度 L (当前分钟内的所有传染源)"]
    I --> J["分钟数 minutes 加 1"]
    J --> K{"循环 L 次 (处理当前层)"}
    K -- "取出队首坐标" --> L["遍历 4 个相邻方向"]
    L --> M{"邻居坐标有效 且 为新鲜橘子?"}
    M -- "是" --> N["该邻居变为腐烂, fresh 减 1, 新坐标入队"]
    M -- "否" --> L
    N --> L
    L -- "4方向遍历完" --> K
    K -- "L次处理完" --> E

---

4. 读题关键词与坑点总结

1. “同时发生”：这是多源 BFS 的核心信号。不能对每个腐烂橘子分别跑一遍 BFS，那样会增加复杂度且逻辑混乱。
2. “最少分钟数”：暗示 BFS 的层数。
3. “不可能完成”：意味着 BFS 结束后，地图上仍有不可达的“1”。
4. 初始即无新鲜橘子：如样例 3，直接返回 0 是容易错过的边界。
5. 最后一分钟的计数：注意，当最后一批新鲜橘子变腐烂入队后，队列虽然不为空，但下一轮由于找不到新鲜橘子，不应再增加分钟数。在代码实现时，建议先检查 fresh 是否已经为 0。

5. 复杂度优化与建议 (NOI 竞赛技巧)

• 坐标压缩：对于这种二维网格，可以将坐标 (r, c) 压缩成一个整数 r * n + c 存入队列，取出时再 x = val / n, y = val % n。这在某些题目中可以简化代码逻辑。
• 原地修改：直接在 grid 数组上将 1 改为 2 来充当 visited 数组的功能，减少内存开销。
• 队列选择：在 C++ 中使用 std::queue<pair<int, int>> 即可满足要求。如果对常数极其敏感，可以手写循环队列。