228 - 994 腐烂的橘子

题目

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

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

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

示例 1：

img

输入：[[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. 1 <= grid.length <= 10

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

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

解答

https://leetcode-cn.com/problems/rotting-oranges/solution/yan-du-you-xian-sou-suo-python3-c-by-z1m/

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])
        rotten = {(i, j) for i in range(row)
                  for j in range(col) if grid[i][j] == 2}
        fresh = {(i, j) for i in range(row)
                 for j in range(col) if grid[i][j] == 1}
        time = 0
        while fresh:
            if not rotten:
                return -1
            rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [
                (0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh}
            fresh -= rotten
            time += 1
        return time

Runtime: 44 ms, faster than 93.80% of Python3 online submissions for Rotting Oranges.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Rotting Oranges.