Q994-腐烂的橘子-中等-深度/宽度优先搜索

994. 腐烂的橘子

Question

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

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

1 <= grid.length <= 10

1 <= grid[0].length <= 10

grid[i][j] 仅为 0、1 或 2

Approach 1: 宽度优先搜索

什么情况应当用 BFS

我们都知道 DFS（深度优先搜索）和 BFS（广度优先搜索）。它们各有不同的适应场景。

BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。

再看看这道题的题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS，应该是毫无疑问的了。

如何写（最短路径的） BFS 代码

我们都知道 BFS 需要使用队列，代码框架是这样子的（伪代码）：

while queue 非空:
	node = queue.pop()
    for node 的所有相邻结点 m:
        if m 未访问过:
            queue.push(m)

但是用 BFS 来求最短路径的话，这个队列中第 1 层和第 2 层的结点会紧挨在一起，无法区分。因此，我们需要稍微修改一下代码，在每一层遍历开始前，记录队列中的结点数量 n ，然后一口气处理完这一层的 n 个结点。代码框架是这样的：

depth = 0 # 记录遍历到第几层
while queue 非空:
    depth++
    n = queue 中的元素个数
    循环 n 次:
        node = queue.pop()
        for node 的所有相邻结点 m:
            if m 未访问过:
                queue.push(m)

本题题解

有了计算最短路径的层序 BFS 代码框架，写这道题就很简单了。这道题的主要思路是：

一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。然后进行 BFS 遍历，每个结点的相邻结点可能是上、下、左、右四个方向的结点，注意判断结点位于网格边界的特殊情况。由于可能存在无法被污染的橘子，我们需要记录新鲜橘子的数量。在 BFS 中，每遍历到一个橘子（污染了一个橘子），就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零，说明存在无法被污染的橘子。以下是 Python 版的题解代码：

def orangesRotting(self, grid: List[List[int]]) -> int:
    M = len(grid)
    N = len(grid[0])
    queue = []

    count = 0 # count 表示新鲜橘子的数量
    for r in range(M):
        for c in range(N):
            if grid[r][c] == 1:
                count += 1
            elif grid[r][c] == 2:
                queue.append((r, c))

    round = 0 # round 表示腐烂的轮数，或者分钟数
    while count > 0 and len(queue) > 0:
        round += 1
        n = len(queue)
        for i in range(n):
            r, c = queue.pop(0)
            if r-1 >= 0 and grid[r-1][c] == 1:
                grid[r-1][c] = 2
                count -= 1
                queue.append((r-1, c))
            if r+1 < M and grid[r+1][c] == 1:
                grid[r+1][c] = 2
                count -= 1
                queue.append((r+1, c))
            if c-1 >= 0 and grid[r][c-1] == 1:
                grid[r][c-1] = 2
                count -= 1
                queue.append((r, c-1))
            if c+1 < N and grid[r][c+1] == 1:
                grid[r][c+1] = 2
                count -= 1
                queue.append((r, c+1))

    if count > 0:
        return -1
    else:
        return round

Approach 2: 多源广度优先搜索

由题目我们可以知道每分钟每个腐烂的橘子都会使上下左右相邻的新鲜橘子腐烂，这其实是一个模拟广度优先搜索的过程。所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

回到题目中，假设图中只有一个腐烂的橘子，它每分钟向外拓展，腐烂上下左右相邻的新鲜橘子，那么下一分钟，就是这些被腐烂的橘子再向外拓展腐烂相邻的新鲜橘子，这与广度优先搜索的过程均一一对应，上下左右相邻的新鲜橘子就是该腐烂橘子尝试访问的同一层的节点，路径长度就是新鲜橘子被腐烂的时间。我们记录下每个新鲜橘子被腐烂的时间，最后如果单元格中没有新鲜橘子，腐烂所有新鲜橘子所必须经过的最小分钟数就是新鲜橘子被腐烂的时间的最大值。

以上是基于图中只有一个腐烂的橘子的情况，可实际题目中腐烂的橘子数不止一个，看似与广度优先搜索有所区别，不能直接套用，但其实有两个方向的思路。

一个是耗时比较大且不推荐的做法：我们对每个腐烂橘子为起点都进行一次广度优先搜索，用 dis[x][y][i]dis[x][y][i] 表示只考虑第 ii 个腐烂橘子为起点的广度优先搜索，坐标位于 (x, y) 的新鲜橘子被腐烂的时间，设没有被腐烂的新鲜橘子的 dis[x][y][i]=infdis[x][y][i]=inf ，即无限大，表示没有被腐烂，那么每个新鲜橘子被腐烂的最短时间即为最后的答案就是所有新鲜橘子被腐烂的最短时间的最大值，如果是无限大，说明有新鲜橘子没有被腐烂，输出 -1 即可。

无疑上面的方法需要枚举每个腐烂橘子，所以时间复杂度需要在原先广度优先搜索遍历的时间复杂度上再乘以腐烂橘子数，这在整个网格范围变大的时候十分耗时，所以需要另寻他路。

多源广度优先搜索

思路

观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。

假设这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子（我们令其为超级源点）会在下一秒把这些橘子都变腐烂，而这个腐烂橘子刚开始在的时间是 -1 ，那么按照广度优先搜索的算法，下一分钟也就是第 0 分钟的时候，这个腐烂橘子会把它们都变成腐烂橘子，然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，最后每个新鲜橘子被腐烂的最短时间 dis[x][y] 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。

为了确认是否所有新鲜橘子都被腐烂，可以记录一个变量 cnt 表示当前网格中的新鲜橘子数，广度优先搜索的时候如果有新鲜橘子被腐烂，则 cnt-=1 ，最后搜索结束时如果 cnt 大于 0 ，说明有新鲜橘子没被腐烂，返回 -1 ，否则返回所有新鲜橘子被腐烂的时间的最大值即可，也可以在广度优先搜索的过程中把已腐烂的新鲜橘子的值由 11 改为 22，最后看网格中是否由值为 11 即新鲜的橘子即可。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        R, C = len(grid), len(grid[0])

        # queue - all starting cells with rotting oranges
        queue = collections.deque()
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    queue.append((r, c, 0))

        def neighbors(r, c) -> (int, int):
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if 0 <= nr < R and 0 <= nc < C:
                    yield nr, nc

        d = 0
        while queue:
            r, c, d = queue.popleft()
            for nr, nc in 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

复杂度分析

时间复杂度：即进行一次广度优先搜索的时间，其中 n=grid.length, m=grid[0].length 。
空间复杂度：需要额外的 disdis 数组记录每个新鲜橘子被腐烂的最短时间，大小为，且广度优先搜索中队列里存放的状态最多不会超过 nm 个，最多需要的空间，所以最后的空间复杂度为。