【LeetCode-中等题】994. 腐烂的橘子

题目

该题值推荐用bfs，因为是一层一层的感染，而不是一条线走到底的那种，所以深度优先搜索不适合

方法一：bfs+层序遍历

广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

在该题：假设图中只有一个腐烂的橘子，它每分钟向外拓展，腐烂上下左右相邻的新鲜橘子，那么下一分钟，就是这些被腐烂的橘子再向外拓展腐烂相邻的新鲜橘子，这与广度优先搜索的过程均一一对应，上下左右相邻的新鲜橘子就是该腐烂橘子尝试访问的同一层的节点，路径长度就是新鲜橘子被腐烂的时间。

class Solution {
// 方法一 : bfs   int m = 0;int n = 0;//  全局 格子宽度和长度int minute = 0;//全局  最小分钟数int fulash = 0;// 记录1的个数public int orangesRotting(int[][] grid) {m = grid.length;n = grid[0].length;Queue<int[]> queue = new LinkedList<>();for(int i = 0; i<m ; i++)for(int j = 0; j<n ; j++){if(grid[i][j] == 1 ) fulash++;//记录新鲜橘子的个数if(grid[i][j] == 2 ){grid[i][j] = 2;queue.offer(new int[]{i,j});//将坏橘子坐标数组 存入队列}}//层序遍历while(!queue.isEmpty() && fulash > 0){// 当队列空了 或者 没有新鲜橘子了，停止循环int size = queue.size();minute++;// 一层一层的传染，每传染一层，时间+1for(int i = 0 ; i<size ;i++){int[] mid = queue.poll();int x = mid[0];int y = mid[1];//上if(x+1 < m && grid[x+1][y]== 1 ){fulash--; // 每传染一个，更新新鲜橘子的数量grid[x+1][y] = 2;//将新鲜果子感染queue.offer(new int[]{x+1,y});//将感染的果子加入队列，进行下一层的处理}//下if(x-1 >=0 && grid[x-1][y]== 1 ){fulash--;grid[x-1][y] = 2;queue.offer(new int[]{x-1,y});}//右if(y+1 < n && grid[x][y+1]== 1 ){fulash--;grid[x][y+1] = 2;queue.offer(new int[]{x,y+1});}//左if(y-1 >=0 && grid[x][y-1]== 1 ){fulash--;grid[x][y-1] = 2;queue.offer(new int[]{x,y-1});  }}}if(fulash > 0) return -1;//若还有新鲜橘子  则返回-1else  return minute;//无新鲜橘子  则返回minute}}