AC截图
题目
思路
1. 初始化
首先遍历整个网格：
-
找出所有的初始腐烂橘子，并将它们的位置加入队列。
-
统计新鲜橘子的数量。
2. 特殊情况处理
如果网格中没有任何新鲜橘子，直接返回 0，因为不需要任何时间让橘子腐烂。
3. 广度优先搜索（BFS）
利用BFS进行层次遍历，模拟每一分钟内腐烂的扩散过程：
-
对于队列中的每个腐烂橘子，检查其上下左右四个方向上的邻居。
-
如果邻居是新鲜橘子，则将其变为腐烂，并将其位置加入队列以便在下一分钟继续扩散。
-
每次处理完当前层的所有节点后，增加时间计数器（表示经过了一分钟）。
4. 结果判定
-
如果在遍历结束时，仍有新鲜橘子未被腐烂，返回
-1表示无法使所有橘子腐烂。 -
否则，返回记录的时间计数器作为结果。
代码
class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {queue<pair<int,int>> q;vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};int freshOrange = 0;int res = 0;for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j]==2){q.push({i,j});}else if(grid[i][j]==1){freshOrange++;}}}if(freshOrange==0){return 0;}while(!q.empty() && freshOrange>0){int size = q.size();while(size-->0){auto [x,y] = q.front();q.pop();for(auto dir:directions){int newX = x+dir.first;int newY = y+dir.second;if(newX>=0 && newX<grid.size() && newY>=0 && newY<grid[0].size() && grid[newX][newY]==1){freshOrange--;grid[newX][newY]=2;q.push({newX,newY});}}}res++;}if(freshOrange>0) return -1;else return res;}
};