力扣题/图论/腐烂的橘子
腐烂的橘子
力扣原题
在给定的 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 。
/*** @param {number[][]} grid* @return {number}*/
var orangesRotting = function(grid) {const queue = [] // 腐烂橘子队列， 每一个个item定义为 [行, 列, 腐烂时间]const m = grid.lengthconst n = grid[0].lengthlet freshCount = 0;// 初始化，收集所有腐烂橘子，放入队列中 ，并记录健康橘子总数for(let i = 0; i < m; i++) {for(let j = 0; j < n; j++) {if(grid[i][j] === 2) {queue.push([i, j, 0]) // 定义 [行, 列, 腐烂时间]} else if(grid[i][j] === 1) {freshCount += 1}}}let minMinutes = 0while(queue.length) {const [row, col, minute] = queue.shift()// 当前腐烂上下左右未腐烂的橘子，设置为下一分钟腐烂if(row > 0 && grid[row-1][col] === 1) {grid[row-1][col] = 2 // 设置为腐烂，避免重复计算queue.push([row-1, col, minute + 1])minMinutes = minute + 1 // 更新腐烂最短时长freshCount -= 1 // 新鲜橘子数量-1}if(row < m - 1 && grid[row+1][col] === 1) {grid[row+1][col] = 2queue.push([row+1, col, minute + 1])minMinutes = minute + 1freshCount -= 1}if(col > 0 && grid[row][col-1] === 1) {grid[row][col-1] = 2queue.push([row, col-1, minute + 1])minMinutes = minute + 1freshCount -= 1}if(col < n - 1 && grid[row][col+1] === 1) {grid[row][col+1] = 2queue.push([row, col+1, minute + 1])minMinutes = minute + 1freshCount -= 1}}return freshCount ? -1 : minMinutes};
解题思路
- 先遍历
grid获取到新鲜橘子数量和腐烂橘子位置 腐烂橘子位置放进队列里，每次取队列头部的数据，就能保证一定是当前先腐烂的橘子- 数据中有当前腐烂橘子的
行、列、第几分钟腐烂的信息，找其上下左右位置未腐烂的橘子，将其设置为已腐烂，并定义为当前橘子腐烂分钟数+1，将行列数据和新的腐烂分钟数推入队尾，同时新鲜橘子数-1。队列一定是遍历先腐烂的橘子的，所以最小腐烂时间+1 - 队列为空时，则说明已经没有可以腐烂的橘子了，如果当前新鲜橘子还有，则返回
-1，否则才可返回最小分钟数