leetcode 994.腐烂的橘子

思路：BFS

是典型的BFS题型，只不过这里用来表示腐烂的传染，初次碰见的读者可以这样想：

如果一个人生病了，他会传染给其他跟他接近的人，然后接近他的人感冒了就会传染给其他接近他们的人，依次类推。

这道题就是这样传染病模型，我们实现BFS需要定义队列来实现，初始化的时候首先把0分钟就腐烂的橘子装入队列中，然后再进行BFS遍历比较方便。然后，又定义两个移动数组dy,dx用来判断周围的格子是否符合条件入队。count数组则是记录每个格子橘子腐烂时的时间。因为BFS遍历比较简单，可以直接找模板，这里直接贴代码不详细讲了。

注意：这里作者把0分钟腐烂的橘子在count数组定义中初始化了1，因为一开始创建count数组的时候初始值都是0，这样用于分辨。到最后遍历count最大值之后，再在结果上-1就行了。

如果本来就没有腐烂的橘子，直接返回0.

class Solution {class Node{int x;int y;public Node(int x,int y){this.x=x;this.y=y;}}int [][]count;int []dx={-1,1,0,0};int []dy={0,0,-1,1};Deque<Node>q=new LinkedList<>();public void bfs(int [][]grid){while(!q.isEmpty()){Node n=q.getFirst();q.removeFirst();for(int i=0;i<4;i++){int a=n.x+dx[i];int b=n.y+dy[i];if(a<0||a>=grid.length||b<0||b>=grid[0].length)continue;if(grid[a][b]==0)continue;if(count[a][b]>0)continue;count[a][b]=count[n.x][n.y]+1;Node node=new Node(a,b);q.addLast(node);}}}public int orangesRotting(int[][] grid) {count=new int[grid.length][grid[0].length];for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]==2){count[i][j]=1;Node node=new Node(i,j);q.addLast(node);}}}bfs(grid);int res=0;for(int i=0;i<count.length;i++){for(int j=0;j<count[0].length;j++){if(grid[i][j]==1&&count[i][j]==0){return -1;}res=Math.max(res,count[i][j]);}}if(res==0)return 0;elsereturn res-1;}
}