腐烂的橙子 - “最初有多个腐烂的橙子”案例

Question

您将获得一个 m x n 网格，其中每个单元格可以具有三个值之一：

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

每分钟，任何与腐烂橙子 4 向相邻的新鲜橙子都会腐烂。

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

嗨，我想知道如何修改下面的代码以适应首先有多个烂橙子的情况。预先感谢。

    from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = deque()

        minute = 0
        rows = len(grid)
        cols = len(grid[0])

        offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    q = deque([(i, j)]) # every rotten orange is recorded

        while q:
            for _ in range(len(q)): # the number of originally/newly rotten oranges
                i, j = q.popleft()

                for dx, dy in offsets:
                    x, y = i + dx, j + dy

                    if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1: # have to limit the index
                        grid[x][y] = 2
                        q.append((x, y))

            minute += 1 # after a round of infection from the original rotten oranges
                    
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    return -1 # special case - only fresh orange 

        return max(0, minute-1) # it has to -1 because after all the oranges being infected, minute += 1 again

Answer 1

• 将最短时间设置为 0
• 圈住好橙子
  • 找到坏橙子的最短路径（Dijkstra算法）
  • 如果路径长度 > MINTIME
    • 将 MINTIME 设置为路径长度