994. 腐烂的橘子

994. 腐烂的橘子

题目链接：994. 腐烂的橘子

代码如下：

//广度优先遍历
//参考链接:https://leetcode.cn/problems/rotting-oranges/solutions/2773461/duo-yuan-bfsfu-ti-dan-pythonjavacgojsrus-yfmh
class Solution 
{
public:
    int orangesRotting(vector<vector<int>>& grid) 
    {
        int m=grid.size(),n=grid[0].size();
        int fresh=0;
        vector<pair<int,int>> q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    fresh++;//统计新鲜橘子的个数
                }
                else if(grid[i][j]==2)
                {
                    q.emplace_back(i,j);//把一开始就腐烂的放到队列中
                }
            }
        }
        int res=-1;
        while(!q.empty())
        {
            res++;//过了一分钟
            vector<pair<int,int>> nxt;
            for(auto& [x,y]:q)//遍历已腐烂的橘子
            {
                for(int i=0;i<4;i++)//遍历4个方向
                {
                    int nextX=x+dir[i][0];
                    int nextY=y+dir[i][1];
                    if(nextX<0||nextX>=m||nextY<0||nextY>=n)    continue;
                    if(grid[nextX][nextY]!=1)   continue;
                    fresh--;
                    grid[nextX][nextY]=2;
                    nxt.emplace_back(nextX,nextY);
                }
            }
            q=move(nxt);
        }
        return fresh?-1:max(res,0);
    }
private:
    int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49