1. 題目

在給定的網格中，每個單元格可以有以下三個值之一：

值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。

返回直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -1。

示例 1： 輸入：[[2,1,1],[1,1,0],[0,1,1]] 輸出：4示例 2： 輸入：[[2,1,1],[0,1,1],[1,0,1]] 輸出：-1 解釋：左下角的橘子（第 2 行， 第 0 列）永遠不會腐爛，因為腐爛只會發生在 4 個正向上。示例 3： 輸入：[[0,2]] 輸出：0 解釋：因為 0 分鐘時已經沒有新鮮橘子了，所以答案就是 0 。提示： 1 <= grid.length <= 10 1 <= grid[0].length <= 10 grid[i][j] 僅為 0、1 或 2

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/rotting-oranges
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 圖的廣度優先搜索

• 先將所有腐爛的位置加入隊列，同時記錄好的橘子個數
• 訪問過的位置改為-1（visited標記）
• 對隊列里的腐爛位置開始BFS，不等于-1（沒訪問），且等于1（沒爛的）加入隊列（同時好橘子減1）

class Solution { public:int orangesRotting(vector<vector<int>>& grid) {int i, j, k, len, x, y, goodfruits = 0;int m = grid.size(), n = grid[0].size(), minutes = -1;queue<pair<int,int>> q;for(i = 0; i < m; ++i)for(j = 0; j <n; ++j)if(grid[i][j] == 2){q.push({i,j});//爛橘子入隊grid[i][j] = -1;//訪問過了}else if(grid[i][j] == 1)goodfruits++;//好橘子個數if(goodfruits == 0)return 0;//沒有好橘子，直接返回vector<pair<int,int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};while(!q.empty()){len = q.size();while(len--){for(k = 0; k < 4; ++k){x = q.front().first+dir[k].first;y = q.front().second+dir[k].second;if(x>=0 && x<m && y>=0 && y<n && grid[x][y]!= -1 && grid[x][y]==1){ //沒訪問過 && 是好橘子q.push({x,y});grid[x][y] = -1;//訪問了goodfruits--;//爛了}}q.pop();}++minutes;}if(goodfruits)return -1;//還有好橘子，所以不可能全爛掉return minutes;} };

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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