題目要求
在給定的 m x n 網(wǎng)格 grid 中养交，每個單元格可以有以下三個值之一：
值 0 代表空單元格削茁；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子柿祈。
每分鐘绑莺，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛暖眼。
返回 直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能纺裁，返回 -1 诫肠。
示例1：
輸入：grid = [[2,1,1],[1,1,0],[0,1,1]]
輸出：4
示例 2：
輸入：grid = [[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋：左下角的橘子（第 2 行， 第 0 列）永遠不會腐爛欺缘，因為腐爛只會發(fā)生在 4 個正向上栋豫。
示例 3：
輸入：grid = [[0,2]]
輸出：0
解釋：因為 0 分鐘時已經(jīng)沒有新鮮橘子了，所以答案就是 0 谚殊。
解題思路
這道題和Leetcode 542 思路一樣丧鸯，都可以采用多源BFS的方法。
主要流程如下：
- 選擇所有腐爛的橘子络凿，作為起點
- 將腐爛橘子四周的新鮮橘子骡送，加入隊列
- 記錄遍歷的層數(shù)昂羡，最后一層的橘子就是最后被腐爛的橘子，也就是橘子全部腐爛需要的天數(shù)
Java代碼
class Solution {
// 其實就是求新鮮橘子摔踱，距離腐爛橘子的距離
// 可以用BFS
public int orangesRotting(int[][] grid) {
int n = grid.length, m = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int total = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 2){
queue.offer(new int[]{i, j});
}
if(grid[i][j] == 2 || grid[i][j] == 1){
total++;
}
}
}
// 定義上下左右四個方向
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int level = 0;
int count = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] node = queue.poll();
count++;
for(int k = 0; k < directions.length; k++){
int x = node[0] + directions[k][0];
int y = node[1] + directions[k][1];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
// 如果是新鮮的橘子虐先，加入隊列
if(grid[x][y] == 1){
queue.offer(new int[]{x, y});
// 防止死循環(huán)，需要將橘子設(shè)置為腐爛
grid[x][y] = 2;
}
}
}
level++;
}
// 如果所有的橘子都被遍歷過
if(count == total){
// 如果一個橘子都沒有派敷，直接返回0
return count > 0 ? level - 1 : 0;
}else{
return -1;
}
}
}
總結(jié)
多源BFS的寫法蛹批，需要熟練，可以解決很多類似的問題篮愉。
另外這道題要特別注意邊界case腐芍，包括：
- 有些橘子永遠不會腐爛
- 可能存在一個橘子都沒有的情況
