imashutosh51

Rotten oranges

Jul 23rd, 2022 (edited)
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.24 KB | None | 0 0
  1. from collections import deque
  2.  
  3. class Solution:
  4.     def orangesRotting(self, grid):
  5.         q = deque()
  6.         row, col = len(grid), len(grid[0])
  7.         check = [[False for _ in range(col)] for _ in range(row)]
  8.         total_fresh = 0
  9.         ans = 0
  10.  
  11.         for i in range(row):
  12.             for j in range(col):
  13.                 if grid[i][j] == 2:
  14.                     q.append((i, j))
  15.                     check[i][j] = True
  16.                 if grid[i][j] == 1:
  17.                     total_fresh += 1
  18.  
  19.         while len(q) and total_fresh:
  20.             k = len(q)
  21.             x = [-1, 0, 1, 0]
  22.             y = [0, 1, 0, -1]
  23.  
  24.             for i in range(k):
  25.                 temp = q[0]
  26.                 q.popleft()
  27.  
  28.                 for k in range(4):
  29.                     new_x = temp[0] + x[k]
  30.                     new_y = temp[1] + y[k]
  31.  
  32.                     if (new_x >= 0 and new_y >= 0 and new_x < row and new_y < col
  33.                         and grid[new_x][new_y] == 1 and not check[new_x][new_y]):
  34.                         q.append((new_x, new_y))
  35.                         check[new_x][new_y] = True
  36.                         total_fresh -= 1
  37.  
  38.             ans += 1
  39.  
  40.         if total_fresh != 0:
  41.             return -1
  42.         return ans
  43.  
Advertisement
Add Comment
Please, Sign In to add comment