[多源bfs]leetcode994：腐烂的橘子(medium)

题目：

题解：

思路：多源 bfs，初试在添加源点时，顺便统计橘子的个数，然后再进行 bfs 时，每扩展一层就减去腐烂的橘子就行了。

代码如下：

int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
using PII = pair<int,int>;
class Solution {
public:// 思路：从多个烂橘子开始多源bfs，点(x,y)第一次被访问时就是距离它最近的烂橘子扩展到了这里int orangesRotting(vector<vector<int>>& g) {int n=g.size(),m=g[0].size();int oranges=0;queue<PII> q;for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(g[i][j]>0){oranges++;if(g[i][j]==2)q.push({i,j});}int res=0;// 开始多源bfswhile(q.size()){int len=q.size();// 减去本层的橘子数oranges-=len;for(int i=0;i<len;++i){auto [x,y]=q.front();q.pop();for(int k=0;k<4;++k){int nx=x+dx[k],ny=y+dy[k];if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==1){g[nx][ny]=2;q.push({nx,ny});}}}// 扩展完一圈后，res++if(q.size())res++;}return oranges==0?res:-1;}
};