【广度优先搜索】994. 腐烂的橘子

本文主要是介绍【广度优先搜索】994. 腐烂的橘子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

994. 腐烂的橘子

解题思路

首先将所有腐烂的橘子入队
BFS
针对每一个橘子出队取出行列号然后判断当前位置的上下左右的橘子是否是新鲜橘子
如果是，变成腐烂的橘子然后入队
最后当队列为空判断round

class Solution {public int orangesRotting(int[][] grid) {// BFS 计算最短路径问题  腐烂橘子到所有新鲜的橘子的最短路径int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();// 一开始找出所有腐烂的橘子 作为根节点 入队int count = 0;for(int r = 0;  r< M; r++){for(int c = 0; c < N; c++){if(grid[r][c] == 1){count++;// 计算新鲜橘子}else if(grid[r][c] == 2){queue.add(new int[]{r,c});// 添加腐烂的橘子}}}int round = 0;// round表示腐烂的轮数while(count > 0 && !queue.isEmpty()){round++;int size = queue.size();for(int i = 0; i < size; i++){int[] orange = queue.poll();// 出队 烂橘子// 取出行列号int r = orange[0];int c = orange[1];// 判断上面的橘子是不是新鲜橘子 如果是 变成腐烂橘子  然后入队if(r - 1 >= 0 && grid[r - 1][c] == 1){grid[r - 1][c] = 2;count--;// 新鲜橘子 减一queue.add(new int[]{r - 1,c});}// 下面的 橘子if(r +1 < M && grid[r + 1][c] == 1){grid[r + 1][c] = 2;count--;// 新鲜橘子 减一queue.add(new int[]{r + 1,c});}// 左边的 橘子if(c - 1 >= 0 && grid[r][c - 1] == 1){grid[r][c - 1] = 2;count--;// 新鲜橘子 减一queue.add(new int[]{r,c - 1});}// 右边的橘子if(c +1 < N && grid[r][c + 1] == 1){grid[r][c + 1] = 2;count--;// 新鲜橘子 减一queue.add(new int[]{r,c + 1});}}}if(count > 0){return - 1;// 剩余新鲜橘子 失败}else{return round;}}
}