题目：https://leetcode-cn.com/problems/rotting-oranges/

我的方法一：广度优先搜索

广度优先搜索是从一个点出发，然后遍历完所有的点；
但是该问题需要求的是耗时时间，所以需要从多个点出发，然后分多少轮遍历完所有的点；

步骤：

1. 设置一个good_size，表示好橘子的数量；设置queue，存放腐烂橘子的队列bad_queue
2. 首先遍历所有的点，获得good_size和bad_queue
3. 每次循环（每分钟），获得bad_queue的大小，遍历这些烂橘子，如果一个烂橘子周围的橘子是好橘子，那么将好橘子置为烂橘子，good_size减1，并将烂橘子push到bad_queue中
4. 当good_size为0时结束，表示可以全部腐烂，并返回时间（即循环的次数）；
   如果bad_queue为空，那么说明不能全部腐烂，则返回-1

边界条件

1. good_size为0时停止，表示可以全部腐烂
2. bad_queue为空，表示不能全部腐烂
3. 初始时，bad_queue为空，good_size大于0，返回-1
4. 初始时，bad_queue为空，good_size=0，返回0
5. 初始时，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/
总体思路和我是一样的，队列+广度优先搜索，但是官方实现更加简洁。

1. 我的是双层循环，官方是单层循环
   原因是，官方引入了O(mn)的空间dis来代替我的minutes，我只有一个minutes，所以需要第二层遍历，保证同一个时间的腐烂橘子都将周围的橘子腐烂了。但是如果用dis代表腐烂时间，那么就不用第二层遍历了。
2. 腐烂上下左右四个橘子，官方是使用一个for循环比较巧妙，通过查表的方式获得四个橘子的坐标