在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

**输入：**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

与找岛屿过程类似，从腐烂的橘子出发，向四周扩散，即BFS

注意腐烂的橘子是同时扩散的，所以每次可以先记录队列的大小然后一次性把队列中元素遍历完

可以在最后判断有无剩余新鲜橘子，也可以设置一个遍历记录新鲜橘子总数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int orangesRotting(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2)
                    q.push({i, j});
                else if (grid[i][j] == 1)
                    fresh++;
            }
        }
        int minutes = 0;
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty() && fresh > 0) {
            minutes++;
            int size = q.size();

            for (int i = 0; i < size; i++) {
                auto [curi, curj] = q.front();
                q.pop();

                for (auto &d : dirs) {
                    int ni = curi + d[0], nj = curj + d[1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
                        grid[ni][nj] == 1) {
                        grid[ni][nj] = 2;
                        q.push({ni, nj});
                        fresh--;
                    }
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
};