【leetcode13】

作者

994. 腐烂的橘子

  1. class Solution:
  2.     def orangesRotting(self, grid: List[List[int]]) -> int:
  3.         row=len(grid)
  4.         col=len(grid[0])
  5.         que=deque()
  6.         for i in range(row):
  7.             for j in range(col):
  8.                 if grid[i][j]==2:
  9.                     que.append((i,j))
  10.         res=0
  11.         direction=[(0,1),(0,-1),(1,0),(-1,0)]
  12.         while que:                                #有坏橘子则循环
  13.             is_=False
  14.             size=len(que)
  15.             for i in range(size):        #在某一层bfs
  16.                 r,c=que.popleft()
  17.                 for x,y in direction:    #上下左右四橘子的情况
  18.                     dr=r+x
  19.                     dc=y+c
  20.                     if 0<=dr<row and 0<=dc<col and grid[dr][dc]==1:#判断是否出界，是否新鲜
  21.                         grid[dr][dc]=2
  22.                         que.append((dr,dc))         #被感染的橘子添加到队列里
  23.                         is_=True
  24.             if is_:
  25.                 res+=1  #如果一层橘子已经腐烂，没有必要再计时＋1
  27.         for i in range(row):
  28.             for j in range(col):
  29.                 if grid[i][j]==1:
  30.                     res=-1                                     #最后检查有无不能被感染的橘子
  31.         return res

发表评论