题目描述

在一个给定的网格中，每个格子可以有如下三种值之一：

• 值 0 代表一个空的格子；
• 值 1 代表一个新鲜的橘子；
• 值 2 代表一个腐败的橘子。

每分钟，任何一个和腐败橘子相邻（4-方向）新鲜的橘子会腐败掉。

返回没有格子含有新鲜橘子的最少时间。如果这不可能发生，返回 -1。

样例

输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行，第 0 列）永远都不会腐败，因为腐败仅发生在 4-方向上。

输入：[[0,2]]
输出：0
解释：因为在 0 分钟时已经没有新鲜橘子了，所以答案就是 0。

注意

• 1 <= grid.length <= 10
• 1 <= grid[0].length <= 10
• grid[i][j] 仅为 0、1 或 2。

算法

(宽度优先遍历) $O(nm)$

1. 建立一个二维的 dis 数组，表示腐败发生在这个格子时的最少时间。初始时，dis 所有点都为正无穷。
2. 然后，将所有已经腐败的橘子入队，并修改 dis 数组中对应位置为 0。
3. 然后进行宽度优先遍历，如果目标格子上有橘子，则可以更新对应点的 dis 数组。
4. 当队里为空的时候停止。最后统计一下在非空的格子上，对应的 dis 的最大值是多少。如果最大值为正无穷，则答案为 -1，否则答案就是最大值。

时间复杂度

• 每个格子最多遍历常数次，故时间复杂度为 $O(nm)$。

空间复杂度

• 需要用队列和 dis 数组，故需要 $O(nm)$ 的额外空间。

C++ 代码

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dis(n, vector<int>(m, n * m));

        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 2) {
                    q.push(make_pair(i, j));
                    dis[i][j] = 0;
                }

        while (!q.empty()) {
            auto sta = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int x = sta.first + dx[i], y = sta.second + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0)
                    continue;

                if (dis[x][y] > dis[sta.first][sta.second] + 1) {
                    dis[x][y] = dis[sta.first][sta.second] + 1;
                    q.push(make_pair(x, y));
                }
            }
        }

        int ans = 0;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0)
                    ans = max(ans, dis[i][j]);
            }
        if (ans == n * m)
            ans = -1;
        return ans;
    }
};