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;}
}