Leetcode 994. Rotting Oranges
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: [,,]
Output: 4
Example 2:
Input: [,,]
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: []
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.length <= 10
grid is only 0, 1, or 2.
class Solution:
def orangesRotting(self, grid: List]) -> int:
directions = [, [-1, 0], , ]
queue = []
visited = set()
m = len(grid)
n = len(grid)
level = 0
count = 0
goal = 0
c = 0
for i in range(m):
for j in range(n):
if grid == 2:
queue.append()
visited.add((i, j))
count += 1
goal += 1
if grid == 1:
count += 1
c += 1
if c == 0:
return 0
while queue:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
x = cur
y = cur
for direction in directions:
new_x = x + direction
new_y = y + direction
if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n or grid == 0 or (new_x, new_y) in visited:
continue
if grid == 1 and (new_x, new_y) not in visited:
goal += 1
grid = 2
queue.append()
visited.add((new_x, new_y))
level += 1
if goal == count:
return level
for i in range(m):
for j in range(n):
if grid == 1:
return -1
return level
页:
[1]