题目描述
在给定的网格中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
Example1:
 输入：[[2,1,1],[1,1,0],[0,1,1]] 输出：4
Example2:
输入：[[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
Example3:
输入：[[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
提示
- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- grid[i][j] 仅为 0、1 或 2
解题思路
- 首先看到这个，应该很明显的想到用BFS搜素
- 首先先统计好的橘子的个数
- 遍历一边，将坏了的入队
- 然后遍历这个队列，每遍历一次，这个轮数就加1
- 从中选出与之相邻的，看是否是好的，如果是好的，让其变为坏的
- 这个循环的条件，是一定是有好的，并且这个队列不为空，看看例子3就知道了
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<pair<int, int>> q;
int row = grid.size();
if(row == 0){
return 0;
}
int col = grid[0].size();
if(col == 0){
return 0;
}
int cnt = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == 1){
cnt++;
}else if(grid[i][j] == 2){
q.push(make_pair(i, j));
}
}
}
int res = 0;
while(cnt > 0 && !q.empty()){ // 这个一定要有当前好的橘子个数大于0
res++;
int size = q.size();
for(int i = 0; i < size; i++){
pair<int, int> t = q.front();
q.pop();
int r = t.first;
int c = t.second;
if(r - 1 >= 0 && grid[r - 1][c] == 1){
cnt--;
grid[r - 1][c] = 2;
q.push(make_pair(r - 1, c));
}
if(r + 1 < row && grid[r + 1][c] == 1){
cnt--;
grid[r + 1][c] = 2;
q.push(make_pair(r + 1, c));
}
if(c - 1 >= 0 && grid[r][c - 1] == 1){
cnt--;
grid[r][c - 1] = 2;
q.push(make_pair(r, c - 1));
}
if(c + 1 < col && grid[r][c + 1] == 1){
cnt--;
grid[r][c + 1] = 2;
q.push(make_pair(r, c + 1));
}
}
}
if(cnt != 0){
return -1;
}
return res;
}
};
