【刷题1】LeetCode 994. 腐烂的橘子 java题解

tag:图论 广度优先搜索
https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked

使用广度优先搜索，搜索步数就是分钟数，等到所有橘子都腐烂后，各个橘子腐烂的最长分钟数就是全部都烂的最小分钟数

class Solution {public int orangesRotting(int[][] grid) {int m=grid.length;int n=grid[0].length;int[][] deep=new int[m][n];//烂的时候用了几分钟LinkedList<Integer> list=new LinkedList<>();//bfs的队列for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==2){//烂橘子deep[i][j]=0;//0分钟就烂，一开始就是烂int index=i*n+j;//一维下标list.addLast(index);//存储现有烂的}}}int res=0;int[][] direction={{0,1},{0,-1},{1,0},{-1,0}};//四个方向while(list.size()!=0){int before=list.removeFirst();//取出一个烂橘子，腐蚀他周围的四个int beforei=before/n;//iint beforej=before%n;//jfor(int d=0;d<4;d++){int nexti=beforei+direction[d][0];int nextj=beforej+direction[d][1];//检查越界；是否是可以被腐蚀的新鲜橘子if(nexti>=0&&nextj>=0&&nexti<m&&nextj<n&&grid[nexti][nextj]==1){grid[nexti][nextj]=2;//变烂deep[nexti][nextj]=deep[beforei][beforej]+1;//保存分钟数res=Math.max(res,deep[nexti][nextj]);//最大分钟数更新list.addLast(nexti*n+nextj);//将这个烂橘子加入bfs队列}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1)//还存在新鲜橘子return -1;}}return res;}
}