大家好,我是爱分享的小蓝,欢迎交流指正~ ![](http://zhangshiyu.com/zb_users/upload/2023/04/20230411192902168121254281422.png)
全文目录?
?说在前面
?模板-BFS迷宫⭐
?传送锚点
?思路点拨
?代码详解
?走迷宫Ⅰ⭐
?传送锚点
?思路点拨
?代码详解
?走迷宫Ⅱ⭐
?传送锚点
?思路点拨
?代码详解
?走迷宫Ⅲ⭐
?传送锚点
?思路点拨
?代码详解
?扩散⭐⭐
?传送锚点
?思路点拨
?代码详解
?全球变暖⭐⭐⭐
?传送锚点
?思路点拨
?代码详解
?说在前面
鸽了一个星期的BFS模板,小蓝肝了10小时终于写完啦!q(≧▽≦q)
看了十几份题解,调试了上百次程序,终于把原本四十行的代码,精简压缩成20行模板 \^o^/
但小蓝调试的时候,出现好多BUG,研究了几个小时才找到错误原因解决(ToT)/~~~
如果没有人指导的话,友友很可能会跟我一样,掉到BUG坑里几小时出不来???
所以为了节约友友的宝贵学习时间,多腾出些时间可以出去嗨皮~(╹ڡ╹ )
小蓝把思路,代码,细节,BUG 都写在文章里了(●'◡'●)
朋友只需耐心看完下面的文章即可?
祝大家成功逃出迷宫?
?模板-BFS迷宫⭐
?传送锚点![](http://zhangshiyu.com/zb_users/upload/2023/04/20230411192902168121254245854.png)
?思路点拨
一、参数解释:
M:map地图 G:go走过路径 q=deque():双向队列 q.popleft() 头节点从左边出队
二、详细思路:
1.前期准备,先导入数据结构双向队列deque,然后输入题目要求的一堆参数。
2.初始化,创建双向队列,同时赋初值:迷宫开始坐标(0,0)。
3.模拟队列,x,y分别代表队列里出队结点的x坐标,和y坐标。
4.设置结束条件,遍历到迷宫出口(n-1,m-1),打印步数,打印走过的路径。
5.下一步路,遍历可以走的四个方向,得到下一个坐标(a,b)。
6.判断合理,判断坐标是否越界,是否之前遍历过。
7.迭代赋值:判断合理就进行标记,然后添加到队列最后,路径表上增加此刻的方向。
三、细节注意:
代码模板很细节,稍不注意就会出现BUG!小蓝作为三个坑???都踩过的过来人,
来跟大家数数一共有哪些题目里的大坑(ง •_•)ง(没说到的BUG欢迎评论区一起交流)
第一个坑?:为什么要用双向队列deque,列表list不可以吗?
答:用列表模拟队列,运行速度较慢,答题会超时,得不了满分。
而从collections导入deque运行速度较快,程序不会超时,可以得满分。
第二个坑?:q=deque([(0,0)])怎么这么多的括号?都是啥意思?
([(0,0)])像个三明治,先外面套一层deque()函数小括号,
然后里面夹一层列表中括号[ ],最后再加一层代表坐标点小括号().
第三个坑?:遍历四个方向也啥要注意的?
for i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]:
小蓝调试半天才发现这个错误,为了避免友友掉进同样的坑,小蓝温馨提醒一下要看题目条件:“如果有多条长度相同的最短路径,选择在此表示方法下字典序最小的一个。”
遍历顺序按字典序 D→L→R→U,也就是下↓左←右→上↑。
?代码详解
#BFS-迷宫模板from collections import dequen,m=map(int,input().split())M=[[int(i) for i in input()] for j in range(n)]G=[['']*m for i in range(n)]q=deque([(0,0)])while q: x,y=q.popleft() if x==n-1 and y==m-1: print(len(G[-1][-1])) print(G[-1][-1]) break for i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]: a,b=x+i,y+j if 0<=a<n and 0<=b<m and M[a][b]==0: M[a][b]=1 q.append((a,b)) G[a][b]=G[x][y]+k'''样例输入:3 3001100110样例输出:4RDRD'''
?走迷宫Ⅰ⭐
?传送锚点
010000000100001001110000
?思路点拨
下面这道题就是模板的经典例题,简直是为模板量身定做的ヾ(≧▽≦*)o
假如考场上碰到,别人想个半小时,你直接套个BFS模板,5分钟直接轻松拿捏✪ ω ✪
小蓝建议先自己敲一遍模板,然后稍微改改几个地方,应该就AC了(๑•̀ㅂ•́)و✧
?代码详解
#BFS-迷宫from collections import dequen,m=30,50M=[[int(i) for i in input()] for j in range(n)]G=[['']*m for i in range(n)]q=deque([(0,0)])while q: x,y=q.popleft() if x==n-1 and y==m-1: print(G[-1][-1]) break for i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]: a,b=x+i,y+j if 0<=a<n and 0<=b<m and M[a][b]==0: M[a][b]=1 q.append((a,b)) G[a][b]=G[x][y]+k'''样例输入:010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000样例输出:print('DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR')'''
?走迷宫Ⅱ⭐
?传送锚点
?思路点拨
上面的两题都是求最小路径方向(●'◡'●)
下面两题换个问法:求最小走格子次数(●ˇ∀ˇ●)
需要更改模板里的一些参数?
q=deque([(x1-1,y1-1,0)]) 加一个0代表遍历次数。
x,y,z=q.popleft() 从队列取出来一个结点分为三部分,分别是x坐标,y坐标,和遍历次数。
q.append([a,b,z+1]) 注意迭代时遍历次数z+1。
?代码详解
#BFS-走迷宫Ⅱfrom collections import dequen,m=map(int,input().split())M=[list(map(int,input().split())) for i in range(n)]x1,y1,x2,y2=map(int,input().split())q=deque([(x1-1,y1-1,0)])while q: x,y,z=q.popleft() if x==x2-1 and y==y2-1: print(z) break for i,j in [[1,0],[-1,0],[0,1],[0,-1]]: a,b=x+i,y+j if 0<=a<n and 0<=b<m and M[a][b]==1: M[a][b]=0 q.append((a,b,z+1))if (x,y)!=(x2-1,y2-1): print(-1)'''样例输入:5 5 1 0 1 1 01 1 0 1 1 0 1 0 1 11 1 1 1 11 0 0 0 11 1 5 5样例输出:8'''
?走迷宫Ⅲ⭐
?传送锚点
?思路点拨
下面来到验证题,主要检测上一题的掌握情况~
自己先做一下,学会了上一题很简单,换汤不换药,改改参数就AC了~
?代码详解
#BFS-走迷宫Ⅲfrom collections import dequen,m=map(int,input().split())M=[[i for i in input()] for i in range(n)]q=deque([(0,0,1)])while q: x,y,z=q.popleft() if x==n-1 and y==m-1: print(z) break for i,j in [[1,0],[-1,0],[0,1],[0,-1]]: a,b=x+i,y+j if 0<=a<n and 0<=b<m and M[a][b]=='.': M[a][b]='#' q.append((a,b,z+1))'''样例输入:5 5..####....#.#.##.#.##.#..样例输出:9'''
?扩散⭐⭐
?传送锚点
?思路点拨
前三道迷宫题,只是BFS新手入门题,算是餐前小吃,开开胃~
现在上一道正菜,前年国赛的填空题:扩散。
主要用到两个数据结构:集合,双向队列。
选取集合容器来存储是因为它速度快,选取双向队列还是因为它速度快,
反正速度快就对了,大约半分钟就能跑完φ(* ̄0 ̄)
而如果选取列表可能要跑几分钟,估计考试的时候心态就崩了(っ °Д °;)っ(反正我会崩)
下面简单讲一下思路:
先将小蓝画布上有的4个黑点初始化,存到标记集合V和双向队列q里。
然后开始BFS搜索,如果循环2020次,就结束打印黑格子个数。
遍历四个方向,没标记,增加标记并加入队列。黑格子计数器+1.
?代码详解
#BFS-扩散from collections import deque #导入双向队列V={(0,0),(2020,11),(11,14),(2000,2000)} #V:visited标记集合q=deque([(0,0,0),(2020,11,0),(11,14,0),(2000,2000,0)]) #q:deque双向队列cnt=4 #初始黑格数while q: #队列非空 x,y,z=q.popleft() #(0,0,0) if z==2020: #终止条件 print(cnt) #print(20312088) break #结束循环 for i,j in [[1,0],[-1,0],[0,1],[0,-1]]: #遍历四周 a,b=x+i,y+j #取新坐标 if (a,b) not in V: #没有标记 V.add((a,b)) #增加标记 q.append((a,b,z+1)) #加入队列 cnt+=1 #黑格子+1
?全球变暖⭐⭐⭐
?传送锚点![](http://zhangshiyu.com/zb_users/upload/2023/04/20230411192903168121254348153.png)
?思路点拨
最后一道三星省赛真题,挑战大BOSS了 !(╯‵□′)╯嘟嘟炸弹!•••*~●
总体思路:(≧∀≦)ゞ
从问题出发,题目问:“多少个岛屿会被全部淹没?”
先判断全部淹没的条件:当前格子是是'#',上下左右四个格子都是'.'的岛屿。
基本思路:φ(* ̄0 ̄)
二重循环遍历每一个坐标点,如果遇到岛屿,就进行BFS搜索,满足条件统计相加。
注意细节:(~ ̄▽ ̄)~
因为岛屿是一整个连通块,所以要一块一块地遍历。
(岛屿是指连在一起的###,不是单独的一个岛#)
?代码详解
#BFS-全球变暖from collections import dequen=int(input())M=[[i for i in input()]for j in range(n)]vis=[[0]*n for i in range(n)] #标记列表flag=True #淹没标志def bfs(x,y): global flag q=deque([(x,y)]) #初始化开始遍历的坐标 while q: x,y=q.popleft() if M[x][y+1]=='#' and M[x][y-1]=='#' and M[x+1][y]=='#' and M[x-1][y]=='#': flag=False #如果格子的四个方向有岛屿,中间的高地不会被淹没 for i,j in [(0,1),(0,-1),(1,0),(-1,0)]: a,b=x+i,y+j if vis[a][b]==0 and M[a][b]=='#': vis[a][b]=1 #标记岛屿遍历过了 q.append((a,b)) #遍历下一个岛屿ans=0for i in range(n): #遍历每一个格子 for j in range(n): if vis[i][j]==0 and M[i][j]=='#': flag=True #设置淹没标志 bfs(i,j) #搜索这个格子,判断是否需要更改淹没标志 if flag==True: #如果淹没标志不变 ans+=1 #被淹岛屿数量加1print(ans)'''样例输入:7........##.....##........##...####....###........样例输出:1'''
友友们,备战蓝桥最后10天,一起冲刺省赛一等奖!