LeetCode | 0994. Rotting Oranges腐烂的橘子【Python】

川长思鸟来 2023-07-11 06:08 52阅读 0赞

> 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:**

![format_png][]

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`.

### 问题 ###

[力扣][Link 1]

在给定的网格中，每个单元格可以有以下三个值之一：

*  值 `0` 代表空单元格；
 *  值 `1` 代表新鲜橘子；
 *  值 `2` 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 `-1`。

**示例 1：**

![format_png][]

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

**示例 2：**

输入：[[2,1,1],[0,1,1],[1,0,1]]
    输出：-1
    解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

**示例 3：**

输入：[[0,2]]
    输出：0
    解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

**提示：**

1.  `1 <= grid.length <= 10`
2.  `1 <= grid[0].length <= 10`
3.  `grid[i][j]` 仅为 `0`, `1`, 或 `2`

### 思路 ###

**BFS**

先统计新鲜橘子个数 fresh，并把腐烂橘子个数放在队列 q 中。
    遍历 q，每次弹出队首元素，判断四周有没有新鲜橘子，并变为腐烂，同时加入队列 q，fresh 减 1。
    当 q 为空时表示已经全部腐烂。
    每次遍历都要判断是否还有新鲜橘子剩余，如果没有新鲜橘子剩余，直接返回 minute。
    最后结束遍历，还要单独判断是否有新鲜橘子剩余（防止出现类似示例 2 这种永远不会腐烂的橘子的情况）。

**时间复杂度:** O(n\*m)，n 为行数，m 为列数。  
**空间复杂度:** O(n\*m)，n 为行数，m 为列数。

##### 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链接][GitHub]

[LeetCode]: https://leetcode.com/problems/rotting-oranges/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4uanNkZWxpdnIubmV0L2doL1dvbno1MTMwL015LVByaXZhdGUtSW1nSG9zdC9pbWcvb3Jhbmdlcy5wbmc?x-oss-process=image/format,png
[Link 1]: https://leetcode-cn.com/problems/rotting-oranges/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0994-Rotting-Oranges/0994.py