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.
Solutions
1. BFS
坏一个橘子,其周围的都会坏,很明显这是一个 BFS 的问题。那么所有变坏了的橘子都要存进 queue 里。每一次 while 其实是对当前 queue 里所有的橘子都要判断一下,而对每一个橘子的判断又需要四个方向,这么一次 while 的循环就是一个时间的变质扩张,统计有多少次变质扩张即可。
# Time Complexity: O(nm)
# Space Complexity: O(nm)
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
if not grid:
return -1
r, c = len(grid), len(grid[0])
cnt = 0
queue = collections.deque()
for i in range(r):
for j in range(c):
if grid[i][j] == 1:
cnt += 1
if grid[i][j] == 2:
queue.append((i, j))
# Input: [[0,2]]
# Output: 0
# like this, the res should be initialized to -1
res = -1
while queue:
size = len(queue)
for _ in range(size):
x, y = queue.popleft()
for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
if 0 <= i < r and 0 <= j < c and grid[i][j] == 1:
grid[i][j] = 2
cnt -= 1
queue.append((i, j))
res += 1
return max(res, 0) if cnt == 0 else -1
# Runtime: 56 ms, faster than 92.11% of Python3 online submissions for Rotting Oranges.
# Memory Usage: 13.7 MB, less than 16.67% of Python3 online submissions for Rotting Oranges.
参考解决方案中一种极简的方案,比较优雅:
# Time Complexity: O(nm)
# Space Complexity: O(nm)
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
rotting = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2}
fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}
time = 0
while fresh:
if not rotting: return -1
rotting = {(i+di, j+dj) for i, j in rotting for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)] if (i+di, j+dj) in fresh}
fresh -= rotting
time += 1
return time
# Runtime: 60 ms, faster than 74.97% of Python3 online submissions for Rotting Oranges.
# Memory Usage: 13.9 MB, less than 16.67% of Python3 online submissions for Rotting Oranges.