🔗 腐烂的橘子

题目来源：994. 腐烂的橘子 – 力扣（LeetCode）

---

📌 题目描述

在给定的 m x n 网格 grid 中，每个单元格的值含义如下：

• 0：空单元格
• 1：新鲜橘子
• 2：腐烂橘子

每分钟，所有腐烂橘子会同时将其 上下左右 相邻的新鲜橘子变成腐烂橘子。

要求：返回 直到没有新鲜橘子为止所需的最小分钟数。
若不可能腐烂所有橘子，返回 -1。

---

✅ 示例解析

示例 1：

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

解释：

• 第 0 分钟：初始状态，1 个腐烂橘子；
• 第 1 分钟：感染 2 个；
• 第 2 分钟：再感染 2 个；
• 第 3、4 分钟：逐步感染剩余橘子；
• 第 4 分钟后，无新鲜橘子 → 返回 4。

示例 2：

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

解释：左下角的橘子（第 2 行第 0 列）被空格隔断，无法被感染 → 永远新鲜。

示例 3：

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

解释：初始无新鲜橘子，无需等待 → 返回 0。

---

⚠️ 提示

• m == grid.length，n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] ∈ {0, 1, 2}

📌 网格规模小，但算法需具备通用性（可扩展至更大规模）。

---

💡 解法：多源 BFS（广度优先搜索）—— O(mn) 时间，O(mn) 空间

class Solution {
    private static final int FRESH = 1;   // 新鲜橘子
    private static final int ROTTEN = 2;  // 腐烂橘子
    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        int m = grid.length;
        int n = grid[0].length;

        // 初始化：将所有腐烂橘子入队，统计新鲜橘子数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == FRESH) {
                    freshCount++;
                } else if (grid[i][j] == ROTTEN) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // 若无新鲜橘子，直接返回 0
        if (freshCount == 0) return 0;

        int minutes = 0;

        // 多源 BFS
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            boolean infected = false; // 标记本轮是否有新橘子被感染

            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];

                for (int[] dir : DIRECTIONS) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];

                    // 检查是否越界，且为新鲜橘子
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == FRESH) {
                        grid[nx][ny] = ROTTEN; // 腐烂
                        freshCount--;          // 新鲜数减 1
                        queue.offer(new int[]{nx, ny});
                        infected = true;
                    }
                }
            }

            if (infected) minutes++; // 仅当有新感染时，时间 +1
        }

        // 若仍有新鲜橘子，说明无法全部腐烂
        return freshCount == 0 ? minutes : -1;
    }
}

✅ 关键点：

• 多源 BFS：初始所有腐烂橘子同时作为起点；
• 按层遍历：每分钟处理当前所有腐烂橘子的邻居；
• 计数优化：用 freshCount 跟踪剩余新鲜橘子，避免最后遍历整个网格。

---

📊 复杂度分析

• 时间复杂度：O(m × n)
  每个单元格最多入队一次，BFS 遍历一次网格。
• 空间复杂度：O(m × n)
  最坏情况下（全为腐烂橘子），队列存储所有单元格。

---

🧩 解题思路

为什么用 BFS 而不是 DFS？

• 感染是“同步扩散”：每分钟所有腐烂橘子同时感染邻居；
• BFS 天然支持“按层扩展”，每层对应一分钟；
• DFS 是深度优先，无法自然模拟“并行感染”过程。

多源 BFS 的本质

把所有初始腐烂橘子看作“第 0 层”，它们的邻居是“第 1 层”，依此类推。

这与“从多个起点同时开始的最短路径”问题完全一致。

边界情况处理

情况	处理方式
无新鲜橘子	直接返回 0
有新鲜橘子但无法到达	BFS 结束后 freshCount > 0 → 返回 -1
网格全为空	freshCount = 0 → 返回 0