LC 0994 [M] Rotting Oranges - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=y704fEOx0s0&ab_channel=NeetCode
multi-source BFS
class Solution:
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
elif grid[r][c] == 2:
Q.append([r,c])
DIRS = [0,1],[0,-1],[1,0],[-1,0](/ALawliet/algorithms/wiki/0,1],[0,-1],[1,0],[-1,0)
while Q and fresh > 0: # no fresh is another condition which ends the problem
for i in range(len(Q)):
# add adjacent oranges as well so we need this for loop execute exactly len(Q) times at start
r, c = Q.popleft()
for dr, dc in DIRS:
row, col = dr + r, dc + c
# if in bounds and nonrotten, 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