-
Notifications
You must be signed in to change notification settings - Fork 0
/
rotting_oranges.py
41 lines (37 loc) · 1.47 KB
/
rotting_oranges.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque
from typing import List
class Solution:
"""
Task:
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.
"""
def orangesRotting(self, grid: List[List[int]]) -> int:
q = deque()
time, fresh = 0, 0
ROWS, COLS = len(grid), len(grid[0])
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1: fresh += 1
if grid[r][c] == 2: q.append([r,c])
directions = [[1,0], [-1,0], [0,1], [0,-1]]
while q and fresh > 0:
for i in range(len(q)):
r, c = q.popleft()
for dr, dc in directions:
row, col = dr + r, dc + c
# if in bounds and fresh, make rotten
if (row < 0 or row == len(grid)
or col < 0 or col == len(grid[0])
or grid[row][col] != 1):
continue
grid[row][col] = 2
q.append([row, col])
fresh -= 1
time += 1
return time if fresh == 0 else -1