XingHuiSama の宝藏之地

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

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

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1 。

‍

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

‍

1. 算法核心思想

本段代码采用了一种基于“分层模拟”的广度优先搜索（BFS）变体。其核心目的是计算将网格中所有新鲜橘子（1）转化为腐烂橘子（2）所需的最短时间。

解决本题的关键难点在于避免“同层连环感染”（即在同一分钟内，刚被感染的橘子立刻去感染下一个橘子）。本算法通过读写分离的策略成功规避了该问题：

读取阶段：先完整扫描整个网格，将当前这一分钟内具备传染能力的“老腐烂橘子”坐标统一收集到 queue 数组中。
写入阶段：统一遍历 queue 数组，执行周围四个方向的感染操作。由于执行感染时所依据的传染源是预先收集好的固定集合，因此新生成的腐烂橘子不会在当前分钟内参与二次传染，从而在逻辑上保证了时间的严格递增。

2. 代码逻辑拆解

主控循环 (do-while)：该循环控制时间的推移，每一次完整执行代表 1 分钟的流逝。
第一阶段：状态扫描与源点收集：通过双重 for 循环遍历网格。统计当前新鲜橘子的总数 count，同时将所有腐烂橘子（传染源）的坐标 {i, j} 存入 queue 中。
第二阶段：终止条件判定：
- if (count == lastcount)：若本轮扫描发现新鲜橘子数量与上一分钟完全相同，说明感染过程已经停滞，网格中存在永远无法被感染的新鲜橘子，直接返回 -1。
- if (count == 0)：若新鲜橘子数量归零，说明全部感染完毕，返回已累计的时间 min。
第三阶段：状态更新与执行感染：时间累加 min++，并记录当前的橘子数量为 lastcount。随后遍历 queue 中收集到的所有传染源坐标，调用 func 函数向上下左右四个方向扩散。
第四阶段：重置集合：调用 queue.clear() 清空当前的传染源集合，为下一分钟的扫描做准备。
边界处理函数 func：严格检查上下左右的数组边界，并且仅当目标位置为新鲜橘子（1）时，才将其状态修改为腐烂（2）。

‍

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int count = 1;
        int min = 0;
        int lastcount = -1;

        vector<vector<int>> queue;

         do{
            count = 0;
            int i, j;
            for (i = 0; i < grid.size(); i++) {
                for (j = 0; j < grid[0].size(); j++) {
                    if (grid[i][j] == 1) {
                        count++;
                    }
                    if (grid[i][j] == 2) {
                        queue.push_back({i, j});
                    }
                }
            }

             if (count == lastcount) {
                 return -1;
             }

             if (count == 0) {
                 return min;
             }

             min++;
             lastcount = count;

            for (int k = 0; k < queue.size(); k++) {
                int i = queue[k][0];
                int j = queue[k][1];
                func(grid, i, j);
            }

            queue.clear();

        }while (count != 0);

        return -1;
    }
    void func(vector<vector<int>>& grid, int i, int j) {
        if (i - 1 >= 0 && grid[i - 1][j] == 1) {
            grid[i - 1][j] = 2;
        }
        if (j - 1 >= 0 && grid[i][j - 1] == 1) {
            grid[i][j - 1] = 2;
        }
        if (j + 1 < grid[0].size() && grid[i][j + 1] == 1) {
            grid[i][j + 1] = 2;
        }
        if (i + 1 < grid.size() && grid[i + 1][j] == 1) {
            grid[i + 1][j] = 2;
        }

    }
};

‍

3. 复杂度分析

时间复杂度：**** $O(K \times M \times N)$

其中 $M$ 和 $N$ 为网格的行数和列数， $K$ 为完全腐烂所需的时间（分钟数）。由于在每一分钟内，代码都会通过双重循环完整扫描一次规模为 $M \times N$ 的网格，在最坏情况下（例如网格呈单线蛇形排列，每次只感染一个橘子）， $K$ 会趋近于 $M \times N$ 。因此，最坏时间复杂度为 $O((M \times N)^2)$ 。
空间复杂度：**** $O(M \times N)$

主要空间开销来自于动态数组 queue。在最坏情况下（例如网格中绝大部分均为腐烂橘子），queue 需要存储接近 $M \times N$ 个坐标对。

‍