題目

https://leetcode.com/problems/rotting-oranges/

題解

和 leetcode 542. 01 Matrix | 542. 01 矩陣（圖解，廣度優先搜索） 這道題幾乎沒有區別，直接用 542 的圖，來講一下“感染” 的過程，實際上就是個 BFS

只不過本題的 0,1,2 都被占用了，所以我們用 term=3 開始，標記感染輪數。感染過程中，每一輪 term+1，并且記錄每一輪感染的數量 incr。如果某一輪出現 incr=0，即沒有任何 orange 被感染，則說明感染過程結束，退出循環。

最后，感染完成后，檢查一下矩陣中有沒有剩余 1.

class Solution {public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;int incr = 1; // num of affected in this termint term = 3; // 0, 1, 2 already in use, so we mark 'affected' from term=3. term will incr by 1 in each round.while (incr > 0) {incr = 0;for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == term - 1) { // grid[i][j] == term - 1 means this coordinate is affected in the last termif (i - 1 >= 0 && grid[i - 1][j] == 1) { // affect leftgrid[i - 1][j] = term;incr++;}if (i + 1 < M && grid[i + 1][j] == 1) { // affect rightgrid[i + 1][j] = term;incr++;}if (j - 1 >= 0 && grid[i][j - 1] == 1) { // affect upgrid[i][j - 1] = term;incr++;}if (j + 1 < N && grid[i][j + 1] == 1) { // affect downgrid[i][j + 1] = term;incr++;}}}}term++;}// check no 1for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) return -1;}}return term - 4;} }

總結

以上是生活随笔為你收集整理的leetcode 994. Rotting Oranges | 994. 腐烂的橘子（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。