难度：★★★☆☆
类型：数组
方法：宽度优先搜索，队列

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解答

对于二维数组的小岛类型的问题，常常使用深度优先搜索或宽度优先搜索来解决，而像这样涉及到层次信息的题目，常常使用宽度优先搜索，在实现上，用队列就可以。

我们定义一个函数get_neighbors，用来获取某个点的周围点，在函数内部就对周围点的合法性作出了判断，使用yield代替return的函数实际上是一个生成器，效果和返回列表一样的。

我们准备一个空的队列deque，队列中存放的是一个个的元组，元组中包含三个数值，分别是点的横纵坐标以及当前时间（也就是腐烂中心蔓延的层次数）。换句话说，这个队列，存放的是所有腐烂橘子所在位置，以及各自对应的腐烂时间。

初始状况下，将所有腐烂的橘子添加到队列中。

遍历过程用while实现，对于弹出队列的烂橘子，研究其合法邻居是否存在好橘子，如果存在，则将这个好橘子腐烂掉，并将新的烂橘子连同它腐烂的时间一并添加到队列尾。整个过程直到队列中没有元素了为止。

需要注意的是，如果遍历完成后，某些橘子还没有腐烂，说明这些橘子是独立于腐烂区域的，因此按照题目要求需要返回0。否则返回计数器所统计的腐烂时间d。

class Solution:
    def orangesRotting(self, grid):
        row, column = len(grid), len(grid[0])
        grid = grid
        queue = []

        for r in range(row):
            for c in range(column):
                if grid[r][c] == 2:
                    queue.append((r, c, 0))

        def get_neighbors(r, c):
            for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
                if 0 <= nr < row and 0 <= nc < column:
                    yield nr, nc

        d = 0
        while queue:
            r, c, d = queue.pop(0)
            for nr, nc in get_neighbors(r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    queue.append((nr, nc, d+1))

        if any(1 in row for row in grid):
            return -1
        return d

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析