腐爛的橘子
題目
在給定的網(wǎng)格中，每個單元格可以有以下三個值之一：
值 0 代表空單元格母截；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘赔退，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。
返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)证舟。如果不可能硕旗，返回 -1。
示例 1：
輸入：[[2,1,1],[1,1,0],[0,1,1]]
輸出：4
示例 2：
輸入：[[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋：左下角的橘子（第 2 行女责， 第 0 列）永遠不會腐爛漆枚，因為腐爛只會發(fā)生在 4 個正向上。
示例 3：
輸入：[[0,2]]
輸出：0
解釋：因為 0 分鐘時已經(jīng)沒有新鮮橘子了抵知，所以答案就是 0 墙基。
提示：
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 僅為 0、1 或 2
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotting-oranges
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有刷喜。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)残制，非商業(yè)轉(zhuǎn)載請注明出處。
思路
參照leetcode官方解答有以下領(lǐng)悟:
這種圖的題目就是遍歷問題,是廣度優(yōu)先搜索.可以先將所有初始的腐爛橘子放入隊列,然后依次從隊列中取出腐爛橘子,判斷腐爛橘子方便的橘子,依次變腐爛.最后判斷是否還有新鮮橘子.具體可能還是看代碼容易理解一些.在比較腐爛橘子的四周時,官方的題解有些沒有懂,所以我使用了很好理解的方式.
代碼
class Solution {
class Position{
private Integer x;
private Integer y;
private Integer time;
public Position(Integer x,Integer y,Integer time){
this.x = x;
this.y = y;
this.time = time;
}
}
public int orangesRotting(int[][] grid) {
//首先腐爛橘子的位置需要確定
//其次需要確定有無周圍沒有橘子存在的單獨橘子,如果有,則可以直接返回-1
//大概的想法是先找到腐爛橘子,然后將腐爛橘子周圍的橘子入隊,并依次向后入隊.最后查找是否還有無新鮮橘子即可判斷.
Queue<Position> queue = new LinkedList<>();
int time = 0;
//先找初始的腐爛橘子的位置
for(int i = 0;i < grid.length;i++){
for(int j = 0;j < grid[i].length;j++){
if(grid[i][j] == 2){
Position position = new Position(i,j,time);
queue.add(position);
}
}
}
//依次將原有隊列出隊,然后判斷當(dāng)前節(jié)點的四周是否有新鮮橘子,如果有,則將其入隊.循環(huán)往復(fù)
while(!queue.isEmpty()){
Position position = queue.poll();
//對應(yīng)的四個坐標分別是x-1,y,x+1,y,x,y-1,x,y+1
time = position.time+1;
boolean timeChange = false;
if(position.x-1 >=0 && grid[position.x-1][position.y] == 1){
grid[position.x-1][position.y] = 2;
queue.add(new Position(position.x-1,position.y,time));
timeChange = true;
}
if(position.x+1 <=grid.length-1 && grid[position.x+1][position.y] == 1){
grid[position.x+1][position.y] = 2;
queue.add(new Position(position.x+1,position.y,time));
timeChange = true;
}
if(position.y-1 >=0 && grid[position.x][position.y-1] == 1){
grid[position.x][position.y-1] = 2;
queue.add(new Position(position.x,position.y-1,time));
timeChange = true;
}
if(position.y+1 <=grid[position.x].length-1 && grid[position.x][position.y+1] == 1){
grid[position.x][position.y+1] = 2;
queue.add(new Position(position.x,position.y+1,time));
timeChange = true;
}
if (!timeChange){
time--;
}
timeChange = false;
}
//遍歷原有集合,判斷是否還有新鮮橘子
for(int i = 0;i < grid.length;i++){
for(int j = 0;j < grid[i].length;j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return time;
}
}
