1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution:
def orangesRotting(self, G: List[List[int]]) -> int:
def f(i,j,k):
for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
if 0<=x<M and 0<=y<N and G[x][y]==1:
Q.append((x,y,k+1))
G[x][y]=0
M=len(G)
N=len(G[0])
ans=0
Q=deque()
for i in range(M):
for j in range(N):
if G[i][j]==2:
Q.append((i,j,0))
while Q:
i,j,k=Q.popleft()
ans=max(ans,k)
f(i,j,k)
for i in range(M):
for j in range(N):
if G[i][j]==1:
ans=-1
return ans
|