994.腐爛的橘子

在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。返回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -1

輸入：二維數組
輸出：最短時間
思路：看過題解本題使用BFS，廣度優先算法，首先遍歷數組，找到所有的“2”和“1”，然后統計，將“2”存在隊列中，隊列中的元素是數組，存的是“2”對應坐標，設置變量記錄“1”的數，將所有的“2”存入隊列中然后當做廣度優先遍歷的第0層，然后彈出，并將所能“污染”到的“1”進行“污染”，然后每一個“1”變為“2”，“1”的數量減一，最后判斷是否大于0，大于0則返回最短時間，小于0則返回-1。

class Solution {public int orangesRotting(int[][] grid) {//1的個數int num = 0;//2的坐標Queue<int[]> que = new LinkedList<>();//數組緯度int m = grid.length;int n = grid[0].length;//循環遍歷數組for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 2){que.add(new int[]{i , j});}else if(grid[i][j] == 1){num++;}}}//時間int time = 0;while(num > 0 && !que.isEmpty()){time++;//把2的坐標記錄下來//遍歷2int n1 = que.size();for(int i = 0; i < n1; i++){int[] pos = que.poll();int x = pos[0];int y = pos[1];//判斷邊界和1if(x + 1 < m && grid[x + 1][y] == 1){que.add(new int[]{x + 1, y});grid[x + 1][y] = 2;num--;}if(y + 1 < n && grid[x][y + 1] == 1){que.add(new int[]{x, y + 1});grid[x][y + 1] = 2;num--;}if(x - 1 >= 0 && grid[x - 1][y] == 1){que.add(new int[]{x - 1, y});grid[x - 1][y] = 2;num--;}if(y - 1 >= 0 && grid[x][y - 1] == 1){que.add(new int[]{x, y - 1});grid[x][y - 1] = 2;num--;}}}//還有1，返回-1if(num > 0){return -1;}return time;}
}

注意：此處int n1 = que.size(); for(int i = 0; i < n1; i++){...}不能寫成for(int i = 0; i < que.size(); i++)

如果使用 for(int i = 0; i < que.size(); i++)，隊列大小在循環過程中可能會動態變化，導致邏輯錯誤。
如果使用 int n1 = que.size(); for(int i = 0; i < n1; i++)，隊列大小在循環開始前固定，循環次數不會受到動態變化的影響，邏輯更加穩定。