刷题记录（LeetCode 994.腐烂的橘子）

在给定的 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），同时记录扩展层数（开辟dist[ ][ ]数组）。扩展完毕后，再次遍历，寻找最大的dist[i][j]即可，如果发现还有好橘子，则返回-1。

class Solution {
public:
    int bfs(vector<vector<int>>& grid)
    {
        queue<pair<int, int>> q;
        int dist[13][13];
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[i].size(); j++)
            {
                if(grid[i][j] == 2)
                {
                    q.push(pair(i, j));
                    dist[i][j] = 0;
                }
            }
        }
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
        while(!q.empty())
        {
            pair<int, int> p = q.front();
            q.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = p.first + dx[i], y = p.second + dy[i];
                if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1)
                {
                    q.push(pair(x, y));
                    grid[x][y] = 2;
                    dist[x][y] = dist[p.first][p.second] + 1;
                }
            }
        }
        int max_time = 0;
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[i].size(); j++)
            {
                if(grid[i][j] == 1) return -1;
                max_time = max(max_time, dist[i][j]);
            }
        }
        return max_time;
    }

    int orangesRotting(vector<vector<int>>& grid) {
        int res = bfs(grid);
        return res;
    }
};