1from collections import deque
2
3def orangesRotting(grid):
4 if not grid or not grid[0]:
5 return -1
6
7 rows, cols = len(grid), len(grid[0])
8 q = deque()
9 fresh = 0
10
11 # Initialize queue with all rotten oranges; count fresh
12 for r in range(rows):
13 for c in range(cols):
14 if grid[r][c] == 2:
15 q.append((r, c, 0)) # (row, col, minute)
16 elif grid[r][c] == 1:
17 fresh += 1
18
19 if fresh == 0:
20 return 0
21
22 dirs = [(1,0), (-1,0), (0,1), (0,-1)] # Down, Up, Right, Left
23 minutes = 0
24
25 while q:
26 r, c, minutes = q.popleft()
27 for dr, dc in dirs:
28 nr, nc = r + dr, c + dc
29 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
30 grid[nr][nc] = 2 # rot it
31 fresh -= 1
32 q.append((nr, nc, minutes + 1))
33
34 return minutes if fresh == 0 else -1