994. Rotting Oranges (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[inf] * n for _ in range(m)]
        q = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dp[i][j] = -1
                if grid[i][j] == 2:
                    dp[i][j] = 0
                    q.append((i, j))
        seen = set(q)
        depth = 0
        while q:
            depth += 1
            temp = set()
            for (a, b) in q:
                for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
                    x, y = a + dx, b + dy
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1 and (x, y) not in seen:
                        seen.add((x, y))
                        temp.add((x, y))
                        dp[x][y] = depth
            q = temp
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and dp[i][j] == inf:
                    return -1
                result = max(result, dp[i][j])
        return result