1"""
2Do a BFS, and count the iterations
3"""
4
5class Solution:
6 def orangesRotting(self, grid: List[List[int]]) -> int:
7 def step():
8 neigh = set()
9 for i in range(len(grid)):
10 for j in range(len(grid[0])):
11 o = (i, j)
12 if grid[i][j] == 2:
13 if o[0] > 0 and grid[o[0]-1][o[1]] == 1:
14 neigh.add((o[0]-1, o[1]))
15 if o[0] < len(grid)-1 and grid[o[0]+1][o[1]] == 1:
16 neigh.add((o[0]+1, o[1]))
17 if o[1] > 0 and grid[o[0]][o[1]-1] == 1:
18 neigh.add((o[0], o[1]-1))
19 if o[1] < len(grid[0])-1 and grid[o[0]][o[1]+1] == 1:
20 neigh.add((o[0], o[1]+1))
21 for n in neigh:
22 grid[n[0]][n[1]] = 2
23 return bool(neigh)
24 steps = 0
25 while True:
26 if step():
27 steps += 1
28 else:
29 break
30 all_rotten = all(grid[i][j] in [0, 2] for i in range(len(grid)) for j in range(len(grid[0])))
31 return steps if all_rotten else -1