994. 腐烂的橘子
在给定的
m x n 网格 grid 中，每个单元格可以有以下三个值之一：- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4
BFS————来源依旧n老师nettee
count记录新鲜橘子数量，round记录腐败轮数，queue存入坏橘子的坐标(add/offer区别在于队列满时会不会抛异常)
算法流程：
遍历数组遇见新鲜橘子count++，遇见坏橘子存入队列
遍历队列，取出队头元素 向四周腐败（如果是新鲜橘子就污染，新鲜橘子count--，记得判断边界有效）
class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();int count = 0; // 新鲜橘子的数量for(int i = 0;i<M;i++)for(int j = 0;j<N;j++){if(grid[i][j] == 1) count++;if(grid[i][j] == 2) queue.offer(new int[]{i,j});}int round = 0; // 腐烂轮数while(count>0 && !queue.isEmpty()){round++;int n = queue.size();for(int i = 0;i<n;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; // 有新鲜橘子return round; // 没有返回轮数 } }
【记一下，n老师的方法太巧妙了】