• LeetCode994. 腐烂的橘子(C++中等题)


    题目

    在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

    值 0 代表空单元格;
    值 1 代表新鲜橘子;
    值 2 代表腐烂的橘子。
    每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

    返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。

    示例 1:

    输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
    输出:4
    示例 2:

    输入:grid = [[2,1,1],[0,1,1],[1,0,1]]
    输出:-1
    解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
    示例 3:

    输入:grid = [[0,2]]
    输出:0
    解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
     

    提示:

    m == grid.length
    n == grid[i].length
    1 <= m, n <= 10
    grid[i][j] 仅为 0、1 或 2

    思路

    BFS,传播的轮次起始就是距离腐烂橘子的路径长度。腐烂橘子可能不止一个,因此我们需要先将腐烂的橘子插入到队列中,然后进行遍历。初始化时记录好橘子的个数cnt值,然后如果被腐化了,则cnt--,最终若cnt>0则返回-1。

    代码

    1. class Solution {
    2. public:
    3. int orangesRotting(vectorint>>& grid) {
    4. int d[20][20];//距离,传播的轮次
    5. memset(d, -1, sizeof d);
    6. int m = grid.size(), n = grid[0].size();
    7. int cnt = 0;//好橘子的个数
    8. int res = 0;//传播的轮次计数
    9. queueint, int>> q;
    10. //将所有烂橘子作为源点进行遍历
    11. for(int i = 0; i < m; i ++)
    12. for(int j = 0; j < n; j ++)
    13. {
    14. if(grid[i][j] == 2)
    15. {
    16. d[i][j] = 0;
    17. q.push({i, j});
    18. }
    19. else if(grid[i][j] == 1) cnt ++;//好橘子个数加一
    20. }
    21. //进行遍历
    22. while(q.size())
    23. {
    24. auto t = q.front();
    25. q.pop();
    26. int x = t.first, y = t.second;
    27. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    28. for(int i = 0; i < 4; i ++)//遍历四个方位
    29. {
    30. int a = dx[i] + x, b = dy[i] + y;
    31. if(a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1 && d[a][b] == -1)
    32. {
    33. d[a][b] = d[x][y] + 1;
    34. res = max(res, d[a][b]);
    35. q.push({a, b});
    36. cnt --;
    37. }
    38. }
    39. }
    40. if(cnt > 0) return -1;
    41. return res;
    42. }
    43. };

  • 相关阅读:
    Vuex中mutations和actions的区别
    MATLAB算法实战应用案例精讲-【优化算法】榛树搜索算法(HTS)(附MATLAB代码实现)
    Docker网络
    Qt教程 — 3.1 深入了解Qt 控件:Buttons按钮
    基于SSM实现前后端分离在线考试管理系统
    Python3----------抽象(多态、封装、继承等)
    【漏洞复现】泛微e-Weaver SQL注入
    JAVA毕业设计HTML5“忆红楼梦之味”网站设计与实现计算机源码+lw文档+系统+调试部署+数据库
    spring cron表达式源码分析
    STM32(垃圾桶开关盖)
  • 原文地址:https://blog.csdn.net/falldeep/article/details/128112260