NC398 腐烂的苹果

题目来源：牛客

题目描述：

给定一个 𝑛×𝑚 n×m  的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围： 1≤𝑛,𝑚≤1000 1≤n,m≤1000  ，网格中的值满足 0≤𝑣𝑎𝑙≤2 0≤val≤2 

 代码：

int rotApple(vector<vector<int> >& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int x_move[] = {0,1,0,-1};//规定传染顺序为右，下，左，上
        int y_move[] = {1,0,-1,0};
        queue<pair<int,int>> q;
        for(int i = 0;i<n;i++)//将bad apple 入队列
        {
            for(int j = 0;j<m;j++)
            {
                if(grid[i][j] == 2)
                {
                    q.push({i,j});
                }
            }
        }
        int mint = 0;//时间
        while(!q.empty())
        {
            mint++;
            int size = q.size();
            while(size--)
            {
                auto [xb,yb] = q.front();//记录bad apple 位置
                for(int i = 0;i<4;i++)
                {
                    int x = xb + x_move[i];//记录要感染苹果的坐标
                    int y = yb + y_move[i];
                    if(x>=0 && x<n && y>=0 && y<m && grid[x][y] == 1)
                    {
                        q.push({x,y});// 被传染的入队列
                        grid[x][y] = 2;//置为bad apple
                    }
                }
                q.pop();
            }
        }
        for(int i = 0;i<n;i++)
        {
            for(int j =0;j<m;j++)
            {
                if(grid[i][j]==1)
                    return -1;
            }
        }
        return mint-1;
    }

 思路：如果大家有注意到的话，其实本题有点像二叉树的层序遍历，我们可以把最初的传染源看作二叉树的根节点，然后不断往下，每个二叉树节点（这里对应感染源）只有两个孩子（这里对应向四个方向传染），二叉树的层序遍历，我们使用队列来完成，这里也是一样，使用队列，一层一层的扩散，最终将所有的苹果传染，如果画图的话会比较容易理解，我们最终需要的是传染的时间，每次扩散一次，时间+1，对应的就是二叉树遍历到下一层

网格里黑色的代表坏苹果，红色代表正常的，我们将坏苹果入队列

然后只要队列里元素，我们就不断循环

这是第一次传染，我们把四个方向的苹果传染，也就是四个方向的苹果入队列，同时我们让传染源出队列，依次重复扩散，即可解决问题

102.二叉树的层序遍历-C++_102.二叉树的层序遍历 c++-CSDN博客

这里有二叉树的层序遍历供大家参考