簡單的廣度優先搜索（BFS）問題：用佇列存盤每批腐爛的橘子，按批次取出腐爛的橘子，取出腐爛橘子的同時放入由新鮮變腐爛的橘子，
import java.util.LinkedList;
import java.util.Queue;
class Solution {
int[][] dist = {{-1,0},{1,0},{0,1},{0,-1}};//上下左右四個方向
public int orangesRotting(int[][] grid) {
int time = 0;//計時
Queue<int[]> queue = new LinkedList<int[]>();
int n = grid.length;
int m = grid[0].length;
boolean[][] booleans = new boolean[n][m];
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(grid[i][j] == 2){//首批腐爛的橘子賦值為true，防止重復遍歷
queue.offer(new int[]{i,j});//腐爛的橘子加入佇列
booleans[i][j] = true;
}
if(grid[i][j] == 0){//空單元格不做處理，防止遍歷設值為true
booleans[i][j] = true;
}
}
}
int[] a = new int[2];
while(!queue.isEmpty()){
int num = queue.size();//每批腐爛橘子的個數
int flag = 0;//若腐爛橘子能感染新鮮的橘子就改變flag的值，
for(int number = 0;number < num;number++){
a = queue.poll();
for(int i = 0;i < 4;i++){
int x = a[0] + dist[i][0];
int y = a[1] + dist[i][1];
if(x>=0&&y>=0&&x<n&&y<m&&booleans[x][y]!=true){
grid[x][y] = 2;
queue.offer(new int[]{x,y});
booleans[x][y] = true;
flag = 1;
}
}
}
if(flag == 1){
time++;
}
}
//遍歷所有單元格，若存在新鮮橘子則回傳-1，否則回傳時間，
for(int i = 0; i < n;i++){
for(int j = 0;j < m;j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return time;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/388414.html
標籤：其他
下一篇：關于剛畢業的程式員考取mba