994. 腐烂的橘子
4 min
题目
解法：多源BFS
思路
第一段：本题采用多源BFS（广度优先搜索）模拟橘子腐烂过程，从所有初始腐烂橘子同时开始层次遍历。
第二段：该方法正确是因为BFS保证按时间顺序传播——第0层是初始腐烂橘子，第1层是一分钟后被感染的橘子，以此类推。多源BFS确保所有腐烂橘子并行传播，符合题目设定。若BFS结束后仍有新鲜橘子，说明其被空格隔离无法腐烂，故返回-1。
第三段：
- Step 1: 遍历网格，将所有腐烂橘子坐标加入队列，统计新鲜橘子数量
- Step 2: 若新鲜橘子数为0，直接返回0
- Step 3: 进行BFS层次遍历，处理当前队列中所有腐烂橘子
- Step 4: 对每个腐烂橘子，检查四个方向，感染新鲜橘子并加入队列
- Step 5: 每完成一层遍历，若发生感染则分钟数+1
- Step 6: BFS结束后，若还有新鲜橘子返回-1，否则返回分钟数
复杂度
- 时间复杂度: ，其中m、n为网格行列数。每个格子最多被访问一次。
- 空间复杂度: ，最坏情况下队列需存储所有橘子位置。
代码
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
// 1. 初始化：找到所有坏橘子，统计新鲜橘子数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) return 0; // 没有新鲜橘子，直接返回0
int minutes = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 2. BFS 腐烂过程
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
// 1. 初始化：找到所有坏橘子，统计新鲜橘子数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) return 0; // 没有新鲜橘子，直接返回0
int minutes = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 2. BFS 腐烂过程
while (!q.empty()) {
int size = q.size();
bool rotten_this_minute = false;
for (int k = 0; k < size; k++) {
auto [r, c] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dirs[i][0];
int nc = c + dirs[i][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 2; // 腐烂
fresh--;
q.push({nr, nc});
rotten_this_minute = true;
}
}
}
if (rotten_this_minute) {
minutes++;
}
}
return fresh == 0 ? minutes : -1;
}
};