hot100-48腐烂的橘子

代码学习的是小红书的尼布斯老师，写的好好，思路写的也好好，很清晰易懂。

力扣的代码学习主要参考小红书的尼布斯老师和小熊饼干老师。

一、题目

m x n 的网格 grid 中，每个单元格可以有三个值：0、1、2。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

二、思路

1、DFS是一条路走到黑，从一个腐烂橘子出发，先一路向下感染到底，再回溯。无法保证同一时间被感染的橘子在同一轮处理。所以这道题要用BFS，逐层遍历，按时间层推进。【多源BFS】

2、遍历网格，将腐烂的橘子加入队列，并且新鲜的橘子计数统计。如果新鲜的橘子为0，那么腐烂的时间为0。如果队列不为空，就BFS传播，从队列中取出当前腐烂的橘子，并将四周的橘子变腐烂。处理一个队列就minutes++。最后判断新鲜橘子剩余那么返回-1，不剩余则返回minutes。

三、代码

class Solution { public int orangesRotting(int[][] grid) { int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}}; LinkedList<int[]> queue = new LinkedList<>(); int m = grid.length, n = grid[0].length; int freshCount = 0; for(int i =0;i<m;i++){ for(int j = 0; j<n;j++){ if(grid[i][j] == 2){ queue.offer(new int[] {i,j}); }else if(grid[i][j] == 1){ freshCount++; } } } if(freshCount ==0) return 0; int minutes = -1; while(!queue.isEmpty()){ int size = queue.size(); for(int k = 0;k<size;k++){ int[] cur = queue.poll(); int x = cur[0],y = cur[1]; for(int[] d : dirs){ int nx = x + d[0],ny = y+d[1]; if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny] == 1){ grid[nx][ny] = 2; freshCount--; queue.offer(new int[]{nx,ny}); } } } minutes++; } return freshCount == 0 ? minutes :-1; } }