【LeetCode-中等】994. 腐烂的橘子 - BFS

994. 腐烂的橘子


解法：BFS
思路与116. 填充每个节点的下一个右侧节点指针有相通之处。
注意网格中没有腐烂的橘子的情况（如[[0]]，[[1]]），前者结果应为0，后者结果为-1。

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<vector<int>> see(n,vector<int>(m));queue<pair<int,int>> q;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==2){q.emplace(i,j);see[i][j]=1;}}}int minute=-1;//没有腐烂的橘子；if(q.empty()) minute=0;while(!q.empty()){int dx[4]={0,1,-1,0};int dy[4]={1,0,0,-1};int size=q.size();for(int i=0;i<size;i++){auto [x,y]=q.front();q.pop();for(int j=0;j<4;j++){int mx=x+dx[j];int my=y+dy[j];if(mx>=0 && mx<n && my>=0 && my<m && grid[mx][my]==1 && see[mx][my]!=1){grid[mx][my]=2;q.emplace(mx,my);see[mx][my]=1;}}}minute++;}//是否还有未被腐烂的橘子for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==1){return -1;}}}return minute;}
};