# Leetcode [No. 994] Rotting Oranges (MEDIUM) 解題心得
+ Blind 169 Challenge Solved on 2024/02/13
+ Second solved on Neetcode150 on 2025/02/26
## 題目
https://leetcode.com/problems/rotting-oranges/description/
## 思路
+ 先說這個解法看似正確但答案會是錯的
+ 首先看到這個題目就應該要想到要使用BFS來做擴散，因為他會是levelOrder的去計算level
+ 所以要先造訪grid上的每一個(x,y)來去計算Rotten orange的位置，在這裡我使用pair來儲存x,y，就不需要另外設計資料結構。
+ 先承認cntFresh這個寫法是看solution看到的，先存著fresh orange的數量之後會非常好用。
```c++=
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
// use BFS to 4-directionally adjacent to a rotting oranges
queue<pair<int,int>> q;
int cntFresh = 0;
for(int i = 0 ; i < grid.size(); i++)
{
for(int j = 0 ; j < grid[i].size(); j++)
{
if(grid[i][j] == 2)
{
q.push(pair<int,int>(i,j));
}
else if (grid[i][j] == 1)
{
cntFresh ++;
}
}
}
if(cntFresh == 0) return 0;
if(q.empty()) return -1;
int cnt = 0;
while(!q.empty())
{
int qSize = q.size();
cout << "qSize = " << qSize << endl;
for(int i = 0 ; i < qSize; i++)
{
pair<int,int> cur = q.front(); // (row,col)
q.pop();
cout << "Cur: " << cur.first << "," << cur.second << endl;
// perform BFS here
grid[cur.first][cur.second] = 2; // rotting this orange.
if(cur.first + 1 < grid.size() && grid[cur.first+1][cur.second] == 1)
{
cout << "Add cur.first+1" << endl;
q.push(pair<int,int>(cur.first+1, cur.second));
}
if(cur.second + 1 < grid[0].size() && grid[cur.first][cur.second+1] == 1)
{
cout << "Add cur.second+1" << endl;
q.push(pair<int,int>(cur.first, cur.second+1));
}
if(cur.first - 1 >= 0 && grid[cur.first-1][cur.second] == 1)
{
cout << "Add cur.first-1" << endl;
q.push(pair<int,int>(cur.first-1, cur.second));
}
if(cur.second - 1 >= 0 && grid[cur.first][cur.second-1] == 1)
{
cout << "Add cur.second-1" << endl;
q.push(pair<int,int>(cur.first, cur.second-1));
}
}
cnt++;
}
// After perform BFS, if there exist any fresh orange, return -1
for(int i = 0 ; i < grid.size(); i++)
{
for(int j = 0 ; j < grid[i].size(); j++)
{
if(grid[i][j] == 1)
{
return -1;
}
}
}
return cnt -1; // cnt-1 implies BFS at least check once
}
};
```
+ 那這個寫法最大的問題出現在BFS這一塊。
+ 具體來說出現的問題在這個case：
+ grid = [[2,2],[1,1],[0,0],[2,0]]
+ 把他畫成圖後會長這個樣子：
+ 
我也把debug訊息記錄下來了。如下所示，其實就是在perform BFS的時候，我們row[0]的2,2會傳染給下排的1,1，所以第一次iteration都有正常執行，但第二次iteration，因為queue有先後問題，所以"grid[1][0]的1傳染給grid[1][1]了"，但是grid[1][1]早在上一個iteration就該被grid[0][1]所傳染。
```=
// first iteration{
qSize = 3
Cur: 0,0
Add cur.first+1
Cur: 0,1
Add cur.first+1
Cur: 3,0
}
// second iteration{
qSize = 2
Cur: 1,0
Add cur.second+1
Cur: 1,1
}
qSize = 1
Cur: 1,1
```
因此最大的問題應該是在儲存grid[cur.first][cur.second]=2這邊出了問題，我們不應該等到q=curNode的時候才把它設為2，而是在看到有fresh orange的時候就該先下手為強！！否則遇到連續的fresh orange就會出事～
### 執行結果
## 改良:
+ 檢查有沒有剩下的orange，也可以用`cntFresh`來直接記數就好
```C++=
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
// use BFS to 4-directionally adjacent to a rotting oranges
queue<pair<int,int>> q;
int cntFresh = 0;
for(int i = 0 ; i < grid.size(); i++)
{
for(int j = 0 ; j < grid[i].size(); j++)
{
if(grid[i][j] == 2)
{
q.push(pair<int,int>(i,j));
}
else if (grid[i][j] == 1)
{
cntFresh ++;
}
}
}
if(cntFresh == 0) return 0; // no fresh, no need to perform BFS
if(q.empty()) return -1; // no rotten orange, can not rotting fresh oranges.
int cnt = 0;
while(!q.empty())
{
int qSize = q.size();
for(int i = 0 ; i < qSize; i++)
{
pair<int,int> cur = q.front(); // (row,col)
q.pop();
// perform BFS here
if(cur.first + 1 < grid.size() && grid[cur.first+1][cur.second] == 1)
{
grid[cur.first+1][cur.second] = 2; // rotting this orange.
q.push(pair<int,int>(cur.first+1, cur.second));
cntFresh--;
}
if(cur.second + 1 < grid[0].size() && grid[cur.first][cur.second+1] == 1)
{
grid[cur.first][cur.second+1] = 2; // rotting this orange.
q.push(pair<int,int>(cur.first, cur.second+1));
cntFresh--;
}
if(cur.first - 1 >= 0 && grid[cur.first-1][cur.second] == 1)
{
grid[cur.first-1][cur.second] = 2; // rotting this orange.
q.push(pair<int,int>(cur.first-1, cur.second));
cntFresh--;
}
if(cur.second - 1 >= 0 && grid[cur.first][cur.second-1] == 1)
{
grid[cur.first][cur.second-1] = 2; // rotting this orange.
q.push(pair<int,int>(cur.first, cur.second-1));
cntFresh--;
}
}
cnt++;
}
// After perform BFS, if there exist any fresh orange, return -1
if(cntFresh>0) return -1;
return cnt -1; // cnt-1 implies BFS at least check once
}
};
```
### 解法分析
+ time complexity: $O(n*m)$
### 執行結果
第二次挑戰
---
+ 用freshCnt來把健康的orange的數量給記錄下來~
```c++=
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<pair<int,int>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int rows = grid.size();
int cols = grid[0].size();
int freshCnt = 0;
// run bfs on rotten orange.
queue<pair<int, int>> q;
for (int i = 0 ; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
q.push({i,j});
} else if (grid[i][j] == 1) {
freshCnt++;
}
}
}
if (q.size() == 0) {
if (freshCnt == 0) {
return 0;
} else {
return -1;
}
}
int res = bfs(q, grid, directions, rows, cols, freshCnt);
return (freshCnt == 0) ? res : -1;
}
bool legal(int row, int col, int rows, int cols) {
if (row >= rows || row < 0 || col >= cols || col < 0) {
return false;
}
return true;
}
int bfs(queue<pair<int,int>>& q, vector<vector<int>>& grid, vector<pair<int,int>>& directions, int rows, int cols, int& freshCnt) {
int time = 0;
while(!q.empty()) {
int size = q.size();
for (int i = 0 ; i < size; i++) {
auto p = q.front();
q.pop();
for (auto dir: directions) {
int new_row = p.first + dir.first;
int new_col = p.second + dir.second;
if (legal(new_row, new_col, rows, cols)) {
if (grid[new_row][new_col] == 1) {
grid[new_row][new_col] = 2;
q.push({new_row, new_col});
freshCnt--;
}
}
}
}
time++;
}
return time - 1; // due to BFS check at least one
}
};
```
Sign in with Wallet
Connect another wallet