# 第74期-基础算法:广度优先搜索 腐烂的橘子
Python是一门需要不断实践练习的编程语言,本文档将AI大学堂学员交流群的Python每周练习进行汇总,希望各位小伙伴能够多进行实践练习,逐渐爱上这门神奇的编程语言,掌握它并在生活中能够使用它。
# 1 问题描述
在给定的网格中,每个单元格可以有以下三个值之一:
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
示例 1:
输入: [[2,1,1],[1,1,0],[0,1,1]]
输出: 4
示例 2:
输入: [[2,1,1],[0,1,1],[1,0,1]]
输出: -1
解释: 左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
示例 3:
输入: [[0,2]]
输出: 0
解释: 因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
初始代码
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
#在此之间填写代码
print(Solution().orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))
print(Solution().orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))
print(Solution().orangesRotting([[0,2]]))
2
3
4
5
6
7
8
# 2 解题思路
- 标签:广度优先搜索 / 深度优先搜索
- 一开始,我们找出所有腐烂的橘子,将它们放入队列,作为第 0 层的结点。
- 然后进行 BFS 遍历,每个结点的相邻结点可能是上、下、左、右四个方向的结点,注意判断结点位于网格边界的特殊情况。
- 由于可能存在无法被污染的橘子,我们需要记录新鲜橘子的数量。在 BFS 中,每遍历到一个橘子(污染了一个橘子),就将新鲜橘子的数量减一。如果 BFS 结束后这个数量仍未减为零,说明存在无法被污染的橘子。
# 3 解题方法
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
a,b=len(grid),len(grid[0])
t=0
queue=[]
for i in range(a):
for j in range(b):
if grid[i][j]==2: queue.append((i,j))
if grid[i][j]==1: t+=1
m=len(queue)
if t==0:return 0
k=m
n=0
for x,y in queue:
for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
if 0<=x+i<a and 0<=y+j<b and grid[x+i][y+j]==1:
grid[x+i][y+j]=2
t-=1
queue.append((x+i,y+j))
m-=1
if m==0:
if t==0:return n
n+=1
m=len(queue)-k
k=len(queue)
return -1
print(Solution().orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))
print(Solution().orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))
print(Solution().orangesRotting([[0,2]]))
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
27
28
29
30
31
第1-3,29-31行: 题目中已经给出的信息,运行代码时要根据这些代码进行编辑
第4行: 定义变量a,b用于存放矩阵横竖长度和宽度
第5行: 定义变量t用于存放为被感染的橘子数量
第6行: 定义列表queue用于存放接下来需要遍历的橘子坐标
第7-8行: for循环遍历所有的橘子和点
第9行: 若该点是腐烂橘子,则将该点加入queue列表中
第10行: 若该点是新鲜橘子,记录新鲜橘子的数量
第11行: 定义变量m记录第一轮腐烂橘子的数量
第12行: 若刚开始就没有新鲜橘子,则直接返回0
第13行: 定义变量k用于记录到此波为止腐烂橘子的数量
第14行: 定义变量n用于存放当前轮数
第15行: 使用for循环遍历queue中腐烂橘子的横竖索引
第16行: 使用for循环遍历腐烂扩散的方向
第17行: 判断扩散的点横竖坐标是否在矩阵内且该处是否有新鲜橘子
第18行: 若是,则将该橘子变成腐烂橘子
第19行: 新鲜橘子数量减一
第20行: queue列表中假如改橘子坐标用于下次扩散
第21行: 当刚才扩散的橘子四周方向遍历完成后,该橘子便无法扩散了,第一轮可扩散的橘子数量减一
第22行: 判断第一轮橘子是否全部扩散完成
第23行: 若已经扩散完成当前轮数加一
第24行: 使用m记录下一轮腐烂扩散的橘子数量
第25行: 使用k记录当前腐烂橘子的总数
第26行: 当没有新鲜橘子的时候,返回轮数
第27行: 若最后还有新鲜橘子,则返回-1
代码运行结果为:
# 算法讲解
这里用到了基础算法:广度优先搜索,简单讲解下这个算法:
广度优先搜索
广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地优先遍历其周围较广的区域,故得名。
树的广度优先遍历
图的广度优先遍历
树与图
# 4 视频解析
高清视频讲解,请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号,发送 python100 即可领取Python基础实战100例源代码