Advertisement
smj007

Untitled

Feb 12th, 2024
779
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.28 KB | None | 0 0
  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))
  19.                         visited.add((r, c))
  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))
  38.                     visited.add((r, c))
  39.                 if grid[r][c] == 1:
  40.                     num_fresh += 1
  41.  
  42.         return bfs(q)
  43.  
  44.  
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement