leetcode hot100 腐烂的橘子
994. 腐烂的橘子
已解答
中等
相关标签
相关企业
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
class Solution(object):
def orangesRotting(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 腐烂时间，实际上就是广度优先搜索的深度
# bfs主要用于解决最短路径的问题，这个最短时间也是一样的。
# 找到 所有 的腐烂句子当做其实节点
# depth = 0
# 下一层+1
queue = []
depth=0
fresh_num = 0
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append([i,j])
if grid[i][j] == 1:
fresh_num+=1
def check(grid,x,y,queue):
if x>=0 and x<m and y>=0 and y<n and grid[x][y]==1:
queue.append([x,y])
grid[x][y]=2
return True
else:
return False
while queue!=[]:
count = len(queue)
for i in range(count):
tmp = queue[0]
del queue[0]
if check(grid,tmp[0]-1,tmp[1],queue):
fresh_num-=1
if check(grid,tmp[0],tmp[1]-1,queue):
fresh_num-=1
if check(grid,tmp[0]+1,tmp[1],queue):
fresh_num-=1
if check(grid,tmp[0],tmp[1]+1,queue):
fresh_num-=1
if len(queue):
depth+=1
if fresh_num>0:
return -1
else:
return depth
这里使用bfs来做，把每一层抽象成腐烂句子就行了