(優先整理熱門100及面試150，不定期持續更新，歡迎關注)

---

994. 腐爛的橘子

在給定的 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

方法：廣度優先搜索 (BFS)

使用 BFS 模擬橘子腐爛過程，記錄每個層次的處理時間。初始隊列包含所有腐爛橘子，每處理完一層后若該層導致新腐爛，則時間加 1。

1. 初始化：遍歷網格，記錄所有腐爛橘子的位置和新鮮橘子數量。
2. 特殊情況：若沒有新鮮橘子，直接返回 0。
3. BFS 處理：逐層處理隊列中的腐爛橘子，腐爛其周圍的新鮮橘子，并記錄時間。
4. 結果判斷：若仍存在未腐爛的新鮮橘子，返回 -1；否則返回總時間。

代碼實現(Java)：

class Solution {public int orangesRotting(int[][] grid) {int rows = grid.length;int cols = grid[0].length;Queue<int[]> queue = new LinkedList<>();int fresh = 0;// 初始化隊列和新鮮橘子計數for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] == 1) {fresh++;}}}// 沒有新鮮橘子直接返回0if (fresh == 0) return 0;int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};int time = 0;while (!queue.isEmpty()) {int size = queue.size();boolean hasRotten = false;// 處理當前層的所有節點for (int i = 0; i < size; i++) {int[] point = queue.poll();for (int[] dir : dirs) {int x = point[0] + dir[0];int y = point[1] + dir[1];// 檢查邊界且是否為新鮮橘子if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {grid[x][y] = 2;queue.offer(new int[]{x, y});fresh--;hasRotten = true;}}}// 若當前層導致腐爛，時間加1if (hasRotten) time++;}// 若仍有新鮮橘子返回-1，否則返回時間return fresh == 0 ? time : -1;}
}

復雜度分析

• 時間復雜度：O(m×n)，每個節點最多被訪問一次。
• 空間復雜度：O(m×n)，隊列在最壞情況下存儲所有腐爛橘子。

---

博客源文件Gitee倉庫:

gitee.com/richardmilos/allen-csdn-notes

(持續更新，未完待續)