算法手记5

修修修也

发布于 2025-03-17 13:44:39

3200

代码可运行

文章被收录于专栏：修也的进阶日记修也的进阶日记

运行总次数：0

代码可运行

一.腐烂的苹果

牛客网题目链接(点击即可跳转):腐烂的苹果_牛客题霸_牛客网

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 多源bfs,每层的坏果入队列,传染完周围的好果就出队列,直到队列为空,传染完毕,传染的层数就是用的时间.最后检查传染完还有没有好果,如果有那直接返回-1即可,否则返回time.

解题代码:

本题解题代码如下:

class Solution {
  public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int rotApple(vector<vector<int> >& grid) 
    {
        //多源bfs+最短路径
        queue<pair<int, int>> q;
        int time = 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});
            }
        }
        //坏果开始bfs传染
        while (!q.empty()) 
        {
            int sz = q.size();//记录本层坏果个数,后续本层坏果传染统一算一分钟
            while (sz--) 
            {
                int x = q.front().first;
                int y = q.front().second;
                for (int i = 0; i < 4; i++) 
                {
                    int xi = x + dx[i];
                    int yi = y + dy[i];
                    if (xi >= 0 && xi < grid.size() && yi >= 0 && yi < grid[0].size() &&grid[xi][yi] == 1) 
                    {
                        grid[xi][yi] = 2;
                        q.push({ xi, yi });
                    }
                }
                q.pop();
            }
            time++;
        }
        //检查有无好果
        for (int i = 0; i < grid.size(); i++) 
        {
            for (int j = 0; j < grid[0].size(); j++) 
            {
                if (grid[i][j] == 1)
                    return -1;
            }
        }
        return time-1;
    }
};