994. Rotting Oranges

Abstract

You are given an m x n grid where each cell can have one of three values:

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

Every minute, any fresh orange that is 4-directionally adjacent 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.

• 給你一組橘子陣列，其中有些橘子爛掉了。
• 每過一分鐘，爛掉的橘子會影響他周圍的橘子也爛掉。
• 請你計算幾分鐘後，這組橘子爛到不能再爛。

Solution

python

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        queue = deque()
        fresh_cnt = 0
        result = 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh_cnt += 1

        if not queue and fresh_cnt > 0:
            return -1

        if not queue:
            return 0

        while(queue):
            queue_len = len(queue)
            for i in range(queue_len):
                rotten = queue.popleft()
                for delta in deltas:
                    x = rotten[0] + delta[0]
                    y = rotten[1] + delta[1]

                    if (x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 1):
                        continue
                    grid[x][y] = 2

                    queue.append((x, y))
                    fresh_cnt -= 1
            result += 1

        if fresh_cnt > 0:
            return -1
        else:
            return result - 1

JS

var orangesRotting = function(grid) {
    deltas = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    queue = [];
    fresh = 0;
    result = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 2) {
                queue.push([i, j]);
            } else if (grid[i][j] == 1) {
                fresh += 1;
            }
        }
    }

    if (queue.length == 0 && fresh > 0) {
        return -1;
    }

    if (queue.length == 0) {
        return 0;
    }

    while(queue.length !== 0) {
        currentQueueLen = queue.length;
        for (let i = 0; i < currentQueueLen; i++) {
            rotten = queue.shift();
            for (let delta of deltas) {
                let x = rotten[0] + delta[0];
                let y = rotten[1] + delta[1];
                if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) {
                    continue
                }
                grid[x][y] = 2; // Rot!
                queue.push([x, y]);
                fresh -= 1;
            }
        }
        result += 1;
    }

    if (fresh > 0) {
        return -1;
    } else {
        return result - 1;
    }
};

檢討

• 跟[[1926. Nearest Exit from Entrance in Maze]]一樣都是針對Graph進行的[[../Algorithm/BFS Searching|BFS Searching]]問題
• 我們先用一個回圈找出一開始就爛掉的橘子的位置
  • 然後把他們塞進queue
  • 同時計算還有多少新鮮的橘子
• 接下來開始在回圈裡面按照BFS的結構去跑
• 跟之前的題型不太一樣的地方有：
  • 不用visited紀錄已經爛掉的位置
  • 一但判定可以爛掉，就直接修改原本的橘子陣列
• 最後是邊界判定，因為有四種情況：
  • 一開始只有新鮮的橘子
    • 所以queue一開始不會有東西
  • 一開始就沒有橘子
    • queue也不會有東西
  • 最後有剩下新鮮的橘子
  • 最後沒有剩下橘子，可以算出多久後爛掉
• 注意y軸的邊界要用grid[0].length或是len(grid[0])定義

Reference