题目描述

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

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

样例

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

算法

(爆搜BFS) $O(mn)$

二维 一轮轮来
1. 一圈一圈往外传播的一般用BFS解，
2. 先找到起始所有腐烂的橘子，然后循环处理，把新腐烂的橘子加入下一次循环的队列中，
3. 当下一次循环的队列为空时，说明不能继续腐烂了，
4. 判断一下还有没有新鲜的橘子，如果有，就返回-1，否则返回分钟数
Round by Round Rotting
| O(T): O(mn) | O(S): O(mn) | Rt: 36ms |

Python 代码

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rst, xlen, ylen = 0, len(grid), len(grid[0])
        if grid[i][j] == 2:
            rot = (i, j) for i in range(xlen) for j in range(ylen)
        fresh = sum(i == 1 for row in grid for i in row)
        while fresh:
            if 0 <= x < xlen and 0 <= y < ylen and grid[x][y] == 1:
                rot = (x, y) for i, j in rot for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)] 
            if not rot:
                return -1
            fresh, rst = fresh - len(rot), rst + 1
            for i, j in rot: 
                grid[i][j] = 2
        return rst