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 。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if not grid :
            return 0
        row=len(grid)
        col=len(grid[0])

        fresh=0
        orqueue=deque()#双端队列

        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    fresh+=1
                elif grid[i][j]==2:
                    orqueue.append((i,j))
        
        dir=[(0,1),(1,0),(0,-1),(-1,0)]
        minutes=0

        while orqueue:
            curr=len(orqueue)
            for _ in range(curr):
                x,y=orqueue.popleft()
                for dx,dy in dir:
                    nx,ny=x+dx,y+dy
                    if 0<=nx<row and 0<=ny<col and grid[nx][ny]==1:
                        grid[nx][ny]=2
                        fresh-=1
                        orqueue.append((nx,ny))
            
            if orqueue:
                minutes+=1
        print(minutes)
        if fresh!=0:
            return -1
        else:
            return minutes