算法手记5

admin管理员组

文章数量:1446760

算法手记5

一.腐烂的苹果

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

题目详情:

本题详情如下图:

---

题目思路:

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

---

解题代码:

本题解题代码如下:

代码语言：javascript代码运行次数：0运行复制

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;
    }
};

---

结语

说点啥好呢...原来被墙的原因是运营商直接把发往外网的请求给扔了...怪不得...好搞笑啊哈哈哈!这道题...让我闻到了一股熟悉的二叉树的味道...所以最终还是忘记它了吗...真的遗憾呐...

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-16，如有侵权请联系 cloudcommunity@tencent 删除前往查看苹果算法gridint队列

本文标签： 算法手记5