📘 題目敘述
給定一個 m x n 的網格 grid，其中：
0代表空格1代表新鮮橘子2代表腐爛橘子
每過 1 分鐘，任何與腐爛橘子「上下左右相鄰」的新鮮橘子都會變腐爛。
請回傳讓所有新鮮橘子都腐爛所需要的最少分鐘數。如果不可能讓所有新鮮橘子都腐爛，回傳 -1。
條件限制
m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 10grid[i][j]只會是0、1、2
🧠 解題思路（一）用vector
我的想法是用 BFS 的概念：
把「目前腐爛的橘子」當成同一層，一分鐘內把它們四周的新鮮橘子全部感染。
感染完一輪就代表過了 1 分鐘，然後再處理下一輪新感染的橘子。
所有變數
m, n：網格大小fresh：目前還剩多少顆新鮮橘子（grid == 1的數量）rotten：用兩個 vector 存所有腐爛橘子的座標rotten[0]存 x（列）rotten[1]存 y（行）
orot：上一輪（上一分鐘）腐爛橘子處理到的位置（index 起點）nrot：目前已知腐爛橘子的總數（index 終點）dx, dy：四方向移動（下、上、右、左）min：已經過了幾分鐘
（我用 orot ~ nrot-1 這段 index 來表示「這一分鐘要擴散的腐爛橘子集合」）
步驟一：先掃一次 grid，統計初始狀態
我先把所有格子掃一遍：
- 遇到
1：fresh++（記錄新鮮橘子數量） - 遇到
2：把座標(i, j)存進rotten，並且nrot++
這樣做完後：
fresh知道還剩多少顆要感染rotten裡面存著「一開始就腐爛」的所有橘子nrot就是初始腐爛橘子的數量
步驟二：用 while 迴圈模擬「一分鐘一層的擴散」
只要 fresh != 0（還有新鮮橘子），就繼續跑：
這一分鐘我會處理哪些腐爛橘子？
我只處理 index 在 [orot, nrot) 的那些腐爛橘子：
orot是上一輪處理的結尾nrot是目前腐爛清單的結尾- 所以
[orot, nrot)就是「這一分鐘要擴散的腐爛橘子」
這樣做的效果等同於 BFS 的分層。
情況一：擴散（感染四周）
對每一顆「這一分鐘要擴散」的腐爛橘子 (x, y)：
- 我看它的四個方向
(xn, yn) - 如果
(xn, yn)在範圍內，且grid[xn][yn] == 1： - 代表是一顆新鮮橘子會被感染
- 把
(xn, yn)加到rotten（變成新的腐爛橘子） fresh--（新鮮橘子減少）grid[xn][yn] = 2（標記成腐爛，避免重複感染）
情況二：這一輪沒有新增腐爛，但 fresh 還沒變 0 → 不可能完成
感染完一輪後，我會檢查：
- 如果
nrot == rotten[0].size()且fresh != 0
意思是：
- 這一輪擴散完之後，腐爛橘子數量完全沒變（沒有新增）
- 但還有新鮮橘子存在
→ 表示剩下的新鮮橘子被隔開了，永遠感染不到，所以直接回傳 -1。
更新到下一分鐘
如果還能繼續：
orot = nrot（下一輪從這裡開始處理）nrot = rotten[0].size()（更新目前腐爛總數）min++（過了 1 分鐘）
最後回傳
當 fresh == 0 時，代表全部都感染完了，回傳 min。（若一開始 fresh == 0，while 不會進去，直接回傳 0）
💻 程式碼實作（一）
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int fresh = 0;
int orot = 0, nrot = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int min = 0;
int xn = 0, yn = 0;
vector<vector<int>> rotten(2);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
fresh = fresh + 1;
} else if (grid[i][j] == 2) {
nrot = nrot + 1;
rotten[0].push_back(i);
rotten[1].push_back(j);
}
}
}
while (fresh != 0) {
for (int k = orot; k < nrot; k++) {
int x = rotten[0][k];
int y = rotten[1][k];
for (int l = 0; l < 4; l++) {
xn = x + dx[l];
yn = y + dy[l];
if (xn >= 0 && xn < m && yn >= 0 && yn < n) {
if (grid[xn][yn] == 1) {
rotten[0].push_back(xn);
rotten[1].push_back(yn);
fresh = fresh - 1;
grid[xn][yn] = 2;
}
}
}
}
if (nrot == rotten[0].size() && fresh != 0) {
return -1;
}
orot = nrot;
nrot = rotten[0].size();
min = min + 1;
}
return min;
}
};🧠 解題思路（二）用queue
這題我用 BFS，因為「腐爛擴散」本質就是從所有腐爛點同時往外一層一層擴散，而且題目要的是「最少分鐘數」，也就是最短層數。
我做法的關鍵是「多源 BFS」：
- 一開始把所有腐爛橘子（值為 2）的位置都丟進 queue，代表它們在第 0 分鐘同時開始擴散
- 每處理完 queue 的一整層，就代表過了 1 分鐘
- 在擴散時，遇到新鮮橘子（值為 1）就把它改成腐爛（設成 2），並加入 queue，等下一分鐘繼續擴散
另外我用 fresh 記錄還剩多少新鮮橘子，這樣 BFS 結束後只要看 fresh 是否歸零，就能判斷到底有沒有全部腐爛。
所有變數
count：分鐘數計數器。我用「每跑完一層就 +1」的方式，所以最後回傳的是擴散了幾層（幾分鐘）fresh：目前還剩多少顆新鮮橘子（值為 1）m：列數n：行數x：queue，存待處理格子的 rowy：queue，存待處理格子的 coldx、dy：四方向位移（下、上、右、左）
🪜 主要流程步驟
1. 掃描整張 grid，收集所有起始腐爛點 + 計算 fresh
我先走過整個矩陣：
- 看到
2：把座標放進 queue（多源 BFS 的起點） - 看到
1：fresh++
2. 如果 fresh 一開始就是 0，直接回傳 0
代表根本沒有新鮮橘子要被感染，所以答案就是 0 分鐘。
3. BFS 分層擴散，每一層代表過了 1 分鐘
只要 queue 還不空，就代表目前還有腐爛橘子會繼續往外感染。
我每次先用 s = x.size() 記錄這一層有幾個點，然後 count++，表示「接下來要處理的是下一分鐘會腐爛的擴散」。
4. 對每個腐爛點，往四個方向感染新鮮橘子
對四方向鄰居：
- 如果出界：略過
- 如果是新鮮橘子
grid[nx][ny] == 1： - 把它改成
2（代表它已經腐爛） - 丟進 queue（下一分鐘它也能繼續感染別人）
fresh--（新鮮橘子數量減少）
5. BFS 結束後，用 fresh 判斷答案
- 如果
fresh > 0：代表有些新鮮橘子永遠感染不到，回傳-1 - 否則回傳
count
⏱️ 複雜度
- 時間複雜度：
O(mn)，每個格子最多被放進 queue 一次、處理一次 - 空間複雜度：
O(mn)，最壞情況 queue 可能存很多格子
💻 程式碼實作（二）
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int count = -1, fresh = 0;
int m = grid.size(), n = grid[0].size();
queue<int> x, y;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
x.push(i);
y.push(j);
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) {
return 0;
}
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
while (!x.empty()) {
int s = x.size();
count++;
for (int k = 0; k < s; k++) {
for (int i = 0; i < 4; i++) {
int nx = x.front() + dx[i], ny = y.front() + dy[i];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
} else if (grid[nx][ny] == 1) {
grid[nx][ny] = 2;
x.push(nx);
y.push(ny);
fresh--;
}
}
x.pop();
y.pop();
}
}
if (fresh > 0) {
return -1;
}
return count;
}
};🔗 題目連結
https://leetcode.com/problems/rotting-oranges/