腐烂的橘子

使用的是广度优先搜索

参考了这个解法：

https://leetcode.cn/problems/rotting-oranges/solutions/2773461/duo-yuan-bfsfu-ti-dan-pythonjavacgojsrus-yfmh/?envType=study-plan-v2&envId=top-100-liked

腐烂的橘子 - 力扣（LeetCode）
腐烂的橘子 - 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： * 值 0 代表空单元格； * 值 1 代表新鲜橘子； * 值 2 代表腐烂的橘子。每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。示例 1： [https://assets.leetcode.cn/aliyun-lc-upload/uploads/2019/02/16/oranges.png] 输入：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

orangesRotting（）

 1class Solution
 2{
 3public:
 4    int orangesRotting(vector<vector<int>>& grid)
 5    {
 6        int row = grid.size(), column = grid[0].size();
 7        int time = 0, fresh = 0;
 8        std::vector<std::pair<int, int>> oranges;
 9
10        for(int j = 0; j < column; j++)
11        {
12            for(int i = 0; i < row; i++)
13            {
14                if(grid[i][j] == 2)
15                {
16                    oranges.emplace_back(i, j);
17                }
18                else if(grid[i][j] == 1)
19                {
20                    fresh++;
21                }
22            }
23        }
24
25        while(fresh && !oranges.empty())
26        {
27            time++;
28            std::vector<std::pair<int, int>> next;
29            for(auto& [x, y] : oranges)
30            {
31                for(auto d : dir)
32                {
33                    int next_x = x + d[0], next_y = y + d[1];
34                    if(0 <= next_x && next_x < row && 0 <= next_y && next_y < column && grid[next_x][next_y] == 1)
35                    {
36                        fresh--;
37                        grid[next_x][next_y] = 2;
38                        next.emplace_back(next_x, next_y);
39                    }
40                }
41            }
42            oranges = next;
43        }
44        return fresh ? -1 : time;
45    }
46private :
47    int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
48};

原文：medium