數據結構和算法 - 643，BFS解腐爛的橘子問題－鑽石舞台

問題描述

來源：LeetCode第994題

難度：中等

在給定的mxn網格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解決

題中說的是每個腐爛橘子的上下左右四個方向的新鮮橘子1分鐘之後都會腐爛，一種解決思路就是先找出所有腐爛的橘子把他們放到一個隊列中，下一步遍歷隊列中所有腐爛的橘子，往他們的上下左右四個方向查找，如果有新鮮的橘子，就讓他們腐爛，然後把他們在加入到隊列中……直到隊列為空為止。我們以示例一為例來看一下

我們來看下代碼

publicintorangesRotting(int[][]grid){intm=grid.length;//網格高度intn=grid[0].length;//網格寬度//放腐爛橘子的坐標Queue<int[]>queue=newLinkedList<>();intfresh=0;//新鮮橘子的數量//找出腐爛的橘子for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]==2){//把腐爛的橘子加入到隊列中queue.offer(newint[]{i,j});}elseif(grid[i][j]==1){//新鮮的橘子fresh++;}}}//如果沒有腐爛的橘子，直接返回0if(fresh==0)return0;//計算時間inttimes=-1;//方向數組int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};while(!queue.isEmpty()){//當前隊列中腐爛橘子的數量intsize=queue.size();times++;//需要的時間while(size-->0){int[]poll=queue.poll();//腐爛的橘子//遍歷當前腐爛橘子的上下左右四個方向for(int[]dir:dirs){intx=poll[0]+dir[0];inty=poll[1]+dir[1];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){fresh--;//新鮮橘子數量減1grid[x][y]=2;//讓他腐爛queue.offer(newint[]{x,y});//腐爛之後加入到隊列中}}}}returnfresh==0?times:-1;}