MUYANG GUO / INDEX

LeetCode

LeetCode 994 Rotting Oranges - Medium

994. Rotting Oranges -- Medium

·1 min read·#LeetCode#Medium#Python

994. Rotting Oranges — Medium

Open on LeetCode

Problem

  1. Rotting Oranges -- Medium

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1: Input: [[2,1,1],[1,1,0],[0,1,1]] Output: 4

Example 2: Input: [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3: Input: [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note: 1 <= grid.length <= 10 1 <= grid[0].length <= 10 grid[i][j] is only 0, 1, or 2.

Solution

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = collections.deque()
        fresh_oranges = 0
        ROWS, COLS = len(grid), len(grid[0])
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh_oranges += 1
        queue.append((-1, -1)) # dummy to mark the level
        minutes_elapsed = -1
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        while queue:
            row, col = queue.popleft()
            if row == -1: # finish the round
                minutes_elapsed += 1
                if queue:  #to avoid the endless loop
                    queue.append((-1, -1))
            else:
                for d in directions:
                    neighbor_row, neighbor_col = row + d[0], col + d[1]
                    if ROWS > neighbor_row >= 0 and COLS > neighbor_col >= 0:
                        if grid[neighbor_row][neighbor_col] == 1:
                            grid[neighbor_row][neighbor_col] = 2
                            fresh_oranges -= 1
                            queue.append((neighbor_row, neighbor_col))
        return minutes_elapsed if fresh_oranges == 0 else -1

Comments