题目：https://leetcode-cn.com/problems/rotting-oranges/
我的方法一：广度优先搜索
广度优先搜索是从一个点出发，然后遍历完所有的点；
但是该问题需要求的是耗时时间，所以需要从多个点出发，然后分多少轮遍历完所有的点；
步骤：
- 设置一个good_size，表示好橘子的数量；设置queue，存放腐烂橘子的队列bad_queue
- 首先遍历所有的点，获得good_size和bad_queue
- 每次循环（每分钟），获得bad_queue的大小，遍历这些烂橘子，如果一个烂橘子周围的橘子是好橘子，那么将好橘子置为烂橘子，good_size减1，并将烂橘子push到bad_queue中
- 当good_size为0时结束，表示可以全部腐烂，并返回时间（即循环的次数）；
如果bad_queue为空，那么说明不能全部腐烂，则返回-1
边界条件
- good_size为0时停止，表示可以全部腐烂
- bad_queue为空，表示不能全部腐烂
- 初始时，bad_queue为空，good_size大于0，返回-1
- 初始时，bad_queue为空，good_size=0，返回0
- 初始时，bad_queue不空，good_size=0，返回0
3-5初始化的边界条件容易忘掉
复杂度
时间复杂度：假设矩阵是m*n的，由于每个点最多遍历4次，所以时间复杂度是O(mn)
空间复杂度：bad_queue的大小，应该是O(?)
代码
struct Orange {
int x = -1;
int y = -1;
};
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int good_size = 0;
queue<Orange> bad_queue;
int max_x = grid.size();
int max_y = 0;
for(int i = 0; i < grid.size(); i++){
max_y = grid[i].size();
for(int j = 0; j < grid[i].size(); j++){
if(grid[i][j] == 2){
Orange o;
o.x = i;
o.y = j;
bad_queue.push(o);
}else if(grid[i][j] == 1){
good_size++;
}
}
}
if(bad_queue.size() == 0){
if(good_size>0){
return -1;
}else{
return 0;
}
}
if(good_size==0){
return 0;
}
int bad_queue_size = bad_queue.size();
int minutes = 0;
while(bad_queue.size() > 0) {
minutes++;
bad_queue_size = bad_queue.size();
while(bad_queue_size>0){
Orange o = bad_queue.front();
bad_queue.pop();
{//top
Orange o_good;
o_good.x = o.x;
o_good.y = o.y - 1;
if(o_good.x >=0 && o_good.x<max_x && o_good.y >= 0 && o_good.y < max_y){
if(grid[o_good.x][o_good.y] == 1){
grid[o_good.x][o_good.y] = 2;
good_size--;
bad_queue.push(o_good);
}
}
}
{//right
Orange o_good;
o_good.x = o.x + 1;
o_good.y = o.y;
if(o_good.x >=0 && o_good.x<max_x && o_good.y >= 0 && o_good.y < max_y){
if(grid[o_good.x][o_good.y] == 1){
grid[o_good.x][o_good.y] = 2;
good_size--;
bad_queue.push(o_good);
}
}
}
{//bottom
Orange o_good;
o_good.x = o.x;
o_good.y = o.y + 1;
if(o_good.x >=0 && o_good.x<max_x && o_good.y >= 0 && o_good.y < max_y){
if(grid[o_good.x][o_good.y] == 1){
grid[o_good.x][o_good.y] = 2;
good_size--;
bad_queue.push(o_good);
}
}
}
{//left
Orange o_good;
o_good.x = o.x - 1;
o_good.y = o.y;
if(o_good.x >=0 && o_good.x<max_x && o_good.y >= 0 && o_good.y < max_y){
if(grid[o_good.x][o_good.y] == 1){
grid[o_good.x][o_good.y] = 2;
good_size--;
bad_queue.push(o_good);
}
}
}
bad_queue_size--;
}
if(good_size == 0){
return minutes;
}
}
return -1;
}
};
其他人更好的方法
官方解法
https://leetcode-cn.com/problems/rotting-oranges/solution/fu-lan-de-ju-zi-by-leetcode-solution/
总体思路和我是一样的，队列+广度优先搜索，但是官方实现更加简洁。
- 我的是双层循环，官方是单层循环
原因是，官方引入了O(mn)的空间dis来代替我的minutes，我只有一个minutes，所以需要第二层遍历，保证同一个时间的腐烂橘子都将周围的橘子腐烂了。但是如果用dis代表腐烂时间，那么就不用第二层遍历了。 - 腐烂上下左右四个橘子，官方是使用一个for循环比较巧妙，通过查表的方式获得四个橘子的坐标
