994.md

994. Rotting Oranges

Solution 1 (time O(mn), space O(mn))

# BFS
class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        cnt = 0
        q = deque([])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    q.append((i, j, 0))
                elif grid[i][j] == 1:
                    cnt += 1
        new_dist = 0
        cur_cnt = 0
        while q:
            cur_x, cur_y, cur_dist = q.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_x = cur_x + dx
                new_y = cur_y + dy
                if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
                    continue
                if grid[new_x][new_y] == 1:
                    new_dist = cur_dist + 1
                    grid[new_x][new_y] = 2
                    cur_cnt += 1
                    q.append((new_x, new_y, new_dist))
        if cur_cnt == cnt:
            return new_dist
        else:
            return -1