994.腐烂的橘子

链接：994.腐烂的橘子
难度：Medium
标签：广度优先搜索、数组、矩阵
简介：返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

题解 1 - python

• 编辑时间：2024-05-13
• 执行用时：37ms
• 内存消耗：16.37MB
• 编程语言：python
• 解法介绍：bfs。

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    class Solution:
        def orangesRotting(self, grid: List[List[int]]) -> int:
            n, m = len(grid), len(grid[0])
            count = sum([grid[i][j] == 1 for i in range(n) for j in range(m)])
            if count == 0: return 0
            q = deque([(i, j) for i in range(n) for j in range(m) if grid[i][j] == 2])
            step = 0
            size = len(q)
            while q:
                i, j = q.popleft()
                for dir in dirs:
                    ni, nj = i + dir[0], j + dir[1]
                    if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] == 1:
                        count -= 1
                        grid[ni][nj] = 2
                        q.append((ni, nj))
                size -= 1
                if size == 0:
                    step += 1
                    size = len(q)
            return step - 1 if count == 0 else -1