hot100 994.腐烂的橘子

1.思路/步骤：以下图为例

（1）统计所有初始就腐烂的橘子的位置，加到列表q中，现在q = [(0,0)]。

（2）初始化答案ans = 0，模拟橘子腐烂的过程，不断循环，直到没有新鲜的橘子，或者q为空。

（3）ans加1，在第ans = 1分钟，遍历q中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q更新为这些橘子的位置，现在q = [(0,1),(1,0)]。

（4）ans加1，在第ans = 2分钟，遍历q中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q更新为这些橘子的位置，现在q = [(0,2),(1,1)]。

（5）ans加1，在第ans = 3分钟，遍历q中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q更新为这些橘子的位置，现在q = [(2,1)]。

（6）ans加1，在第ans = 4分钟，遍历q中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q更新为这些橘子的位置，现在q = [(2,2)]。

（7）由于没有新鲜橘子，退出循环。

2.为了判断是否有永远不会腐烂的橘子（如示例2），我们可以统计初始新鲜橘子的个数fresh。在BFS中，每有一个新鲜橘子被腐烂，就把fresh减一，这样最后如果发现fresh＞0，就意味着有橘子永远不会腐烂，返回-1。

3.疑问：如果代码中不在while循环中判断fresh>0，会发生什么？

答：会在腐烂完所有新鲜橘子后，多循环一次，这会导致ans比实际多1。

4.复杂度分析：

（1）时间复杂度：O(mn)，其中m和n分别为grid的行数和列数。

（2）空间复杂度：O(mn)。

附代码：

class Solution { private static final int[][] DIRECTIONS = {{-1,0},{1,0},{0,-1},{0,1}}; //四方向 public int orangesRotting(int[][] grid) { int m = grid.length; int n = grid[0].length; int fresh = 0; List<int[]> q = new ArrayList<>(); for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(grid[i][j] == 1){ fresh++; //统计新鲜橘子的个数 }else if(grid[i][j] == 2){ q.add(new int[]{i,j}); //一开始就腐烂的橘子 } } } int ans = 0; while(fresh > 0 && !q.isEmpty()){ ans++; //经过一分钟 List<int[]> tmp = q; q = new ArrayList<>(); for(int[] pos : tmp){ //已经腐烂的橘子 for(int[] d : DIRECTIONS){ //四方向 int i = pos[0] + d[0]; int j = pos[1] + d[1]; if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1){ //新鲜橘子 fresh--; grid[i][j] = 2; //变成腐烂的橘子 q.add(new int[]{i,j}); } } } } return fresh > 0 ? -1 : ans; } }