区块链技术博客
www.b2bchain.cn

LeetCode994. 腐烂的橘子 BFS广度优先搜索

这篇文章主要介绍了LeetCode994. 腐烂的橘子 BFS广度优先搜索,通过具体代码讲解8503并且分析了LeetCode994. 腐烂的橘子 BFS广度优先搜索的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了LeetCode994. 腐烂的橘子 BFS广度优先搜索。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=8503。具体如下:

https://www.b2bchain.cn/6165.html 

 //在给定的网格中,每个单元格可以有以下三个值之一:  // //  // 值 0 代表空单元格;  // 值 1 代表新鲜橘子;  // 值 2 代表腐烂的橘子。  //  // // 每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。  // // 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。  // //  // // 示例 1:  // //  // // 输入:[[2,1,1],[1,1,0],[0,1,1]] //输出:4 //  // // 示例 2:  // // 输入:[[2,1,1],[0,1,1],[1,0,1]] //输出:-1 //解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。 //  // // 示例 3:  // // 输入:[[0,2]] //输出:0 //解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。 //  // //  // // 提示:  // //  // 1 <= grid.length <= 10  // 1 <= grid[0].length <= 10  // grid[i][j] 仅为 0、1 或 2  //  // Related Topics 广度优先搜索   import sun.misc.Queue;  import java.util.HashMap; import java.util.LinkedList; import java.util.Map;  //leetcode submit region begin(Prohibit modification and deletion) //BFS广度优先搜索 //队列,逐层搜索,感染橘子 class Solution {     // dr,dc 配合使用得到 grid[r][c] 上下左右元素     int[] dr = new int[]{ 1,-1,0,0};     int[] dc = new int[]{0,0,-1,1 };      public int orangesRotting(int[][] grid) {         // 获取二维数组的行数row 和 列数 column         int R = grid.length, C = grid[0].length;           Queue<Integer> queue = new ArrayDeque();         //存储当前层的元素  索引 腐烂时间         Map<Integer, Integer> depth = new HashMap();         for (int r = 0; r < R; ++r)             for (int c = 0; c < C; ++c)                 if (grid[r][c] == 2) {                     int code = r * C + c;  // 转化为索引唯一的一维数组                     queue.add(code); //存储腐烂橘子                     depth.put(code, 0); //存储橘子变为腐烂时的时间,key为橘子的一维数组下标,value为变腐烂的时间                 }          int ans = 0;         while (!queue.isEmpty()) {             int code = queue.remove();             int r = code / C, c = code % C;             for (int k = 0; k < 4; ++k) {                 int nr = r + dr[k];                 int nc = c + dc[k];                 if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {                     grid[nr][nc] = 2;                     int ncode = nr * C + nc;                     queue.add(ncode);                     // 计次的关键 元素 grid[r][c] 的上左下右元素得腐烂时间应该一致                     depth.put(ncode, depth.get(code) + 1);                     ans = depth.get(ncode);                 }             }         }          for(int i=0;i<R;++i)//检查是否还有新鲜橘子             for(int j=0;j<C;++j)                 if(grid[i][j]==1)                     return -1;         return ans;     } }    //leetcode submit region end(Prohibit modification and deletion) 

 

本文地址https://www.b2bchain.cn/?p=8503

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » LeetCode994. 腐烂的橘子 BFS广度优先搜索
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们