994. 腐爛的橘子
在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：
值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。
返回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -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 列）永遠不會腐爛，因為腐爛只會發生在 4 個方向上。
示例 3：
輸入：grid = [[0,2]]
輸出：0
解釋：因為 0 分鐘時已經沒有新鮮橘子了，所以答案就是 0 。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 僅為 0、1 或 2
- BFS：由于需要所有爛橘子同時開始腐爛周圍的橘子，所以使用 bfs。將爛橘子作為起點加入隊列，不斷尋找四周的新鮮橘子，找到后就將其更新為爛橘子加入隊列，遍歷了幾層就相當于全部腐爛需要幾分鐘
-
int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};public int orangesRotting(int[][] grid) {int m = grid.length, n = grid[0].length;Queue<int[]> q = new LinkedList<>();// 初始化爛橘子入隊for(int i = 0; i < m; i++){for(int j = 0; j < n; j++)if(grid[i][j] == 2)q.offer(new int[]{i, j});}int res = 0;while(!q.isEmpty()){for(int k = q.size(); k > 0; k--){int[] idx = q.poll();for(int[] dir : dirs){int x = idx[0] + dir[0], y = idx[1] + dir[1];if(x < 0 || y < 0 || x >= m || y >= n)continue;if(grid[x][y] != 1)continue;q.offer(new int[]{x, y});grid[x][y] = 2;}}// 只有當有新鮮橘子入隊后才說明有橘子被腐爛了// 否則最開始只有爛橘子的時候也會增加 res 了if(!q.isEmpty())res++;}// 如果還有剩余的新鮮橘子說明無法全部腐爛for(int[] g : grid){for(int x : g)if(x == 1)return -1;}return res;}
)
