# Untitled

Feb 12th, 2024
779
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution:
2.     def orangesRotting(self, grid: List[List[int]]) -> int:
3.         n, m = len(grid), len(grid[0])
4.
5.         def bfs(q):
6.
7.             fresh_count = 0
8.             max_l = 0
9.
10.             while q:
11.                 row, col, l = q.popleft()
12.                 max_l = max(max_l, l)
13.                 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
14.                 for (dr, dc) in directions:
15.                     r = row + dr
16.                     c = col + dc
17.                     if r in range(n) and c in range(m) and grid[r][c] == 1 and (r, c) not in visited:
18.                         q.append((r, c, l+1))
20.                         fresh_count += 1
21.
22.             if fresh_count == num_fresh:
23.                 return max_l
24.             else:
25.                 return -1
26.
27.
28.         # add all rotten oranges to queu
29.         from collections import deque
30.         q = deque()
31.         visited = set()
32.         num_fresh = 0
33.
34.         for r in range(n):
35.             for c in range(m):
36.                 if grid[r][c] == 2:
37.                     q.append((r, c, 0))