LeetCode 0994. Rotting Oranges腐爛的橘子【Easy】【Python】【BFS】

Problem

LeetCode

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:

image

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. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2.

問題

力扣

在給定的網(wǎng)格中风瘦，每個單元格可以有以下三個值之一：

• 值 0 代表空單元格习绢；
• 值 1 代表新鮮橘子叛复；
• 值 2 代表腐爛的橘子谒获。

每分鐘，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛钟病。

返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)挫剑。如果不可能或悲，返回 -1。

示例 1：

image

輸入：[[2,1,1],[1,1,0],[0,1,1]]
輸出：4

示例 2：

輸入：[[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋：左下角的橘子（第 2 行怪与， 第 0 列）永遠不會腐爛夺刑，因為腐爛只會發(fā)生在 4 個正向上。

示例 3：

輸入：[[0,2]]
輸出：0
解釋：因為 0 分鐘時已經(jīng)沒有新鮮橘子了分别，所以答案就是 0 遍愿。

提示：

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] 僅為 0, 1, 或 2

思路

BFS

先統(tǒng)計新鮮橘子個數(shù) fresh，并把腐爛橘子個數(shù)放在隊列 q 中耘斩。
遍歷 q沼填，每次彈出隊首元素，判斷四周有沒有新鮮橘子括授，并變?yōu)楦癄€坞笙，同時加入隊列 q，fresh 減 1荚虚。
當(dāng) q 為空時表示已經(jīng)全部腐爛薛夜。
每次遍歷都要判斷是否還有新鮮橘子剩余，如果沒有新鮮橘子剩余版述，直接返回 minute梯澜。
最后結(jié)束遍歷，還要單獨判斷是否有新鮮橘子剩余（防止出現(xiàn)類似示例 2 這種永遠不會腐爛的橘子的情況）渴析。

時間復(fù)雜度: O(n*m)晚伙，n 為行數(shù)，m 為列數(shù)俭茧。
空間復(fù)雜度: O(n*m)咆疗，n 為行數(shù)，m 為列數(shù)恢恼。

Python3代碼

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        fresh = 0
        q = []

        # count fresh oranges and enqueue rotten oranges
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    fresh += 1
                elif grid[i][j] == 2:
                    q.append((i, j))
        
        if fresh == 0:
            return 0
        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        minute = 0
        
        # bfs
        while q:
            if fresh == 0:
                return minute
                
            size = len(q)
            for i in range(size):
                x, y = q.pop(0)
                for d in dirs:
                    nx, ny = x + d[0], y + d[1]
                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] != 1:
                        continue
                    grid[nx][ny] = 2
                    q.append((nx, ny))
                    fresh -= 1
            minute += 1

        if fresh != 0:
            return -1

代碼地址

GitHub鏈接