大家好，我是爱分享的小蓝，欢迎交流指正~

全文目录🧭

🎁说在前面

🏆模板-BFS迷宫⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🏆走迷宫Ⅰ⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🏆走迷宫Ⅱ⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🏆走迷宫Ⅲ⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🏆扩散⭐⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🏆全球变暖⭐⭐⭐

🚀传送锚点

💡思路点拨

🍞代码详解

🎁说在前面

鸽了一个星期的BFS模板，小蓝肝了10小时终于写完啦！q(≧▽≦q)

看了十几份题解，调试了上百次程序，终于把原本四十行的代码，精简压缩成20行模板 \^o^/

但小蓝调试的时候，出现好多BUG，研究了几个小时才找到错误原因解决(ToT)/~~~

如果没有人指导的话，友友很可能会跟我一样，掉到BUG坑里几小时出不来🕳🕳🕳

所以为了节约友友的宝贵学习时间，多腾出些时间可以出去嗨皮~(╹ڡ╹ )

小蓝把思路，代码，细节，~~BUG~~ 都写在文章里了(●'◡'●)

朋友只需耐心看完下面的文章即可👇

祝大家成功逃出迷宫😎

🏆模板-BFS迷宫⭐

🚀传送锚点

💡思路点拨

一、参数解释：

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 deque
n,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])breakfor i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]:a,b=x+i,y+jif 0<=a<n and 0<=b<m and M[a][b]==0:M[a][b]=1q.append((a,b))G[a][b]=G[x][y]+k
'''
样例输入:
3 3
001
100
110
样例输出:
4
RDRD
'''

🏆走迷宫Ⅰ⭐

🚀传送锚点

💡思路点拨

下面这道题就是模板的经典例题，简直是为模板量身定做的ヾ(≧▽≦*)o

假如考场上碰到，别人想个半小时，你直接套个BFS模板，5分钟直接轻松拿捏✪ ω ✪

小蓝建议先自己敲一遍模板，然后稍微改改几个地方，应该就AC了(๑•̀ㅂ•́)و✧

🍞代码详解

#BFS-迷宫
from collections import deque
n,m=30,50
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(G[-1][-1])breakfor i,j,k in [(1,0,'D'),(0,-1,'L'),(0,1,'R'),(-1,0,'U')]:a,b=x+i,y+jif 0<=a<n and 0<=b<m and M[a][b]==0:M[a][b]=1q.append((a,b))G[a][b]=G[x][y]+k
'''
样例输入:
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
样例输出:
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 deque
n,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)breakfor i,j in [[1,0],[-1,0],[0,1],[0,-1]]:a,b=x+i,y+jif 0<=a<n and 0<=b<m and M[a][b]==1:M[a][b]=0q.append((a,b,z+1))
if (x,y)!=(x2-1,y2-1):print(-1)
'''
样例输入:
5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
样例输出:
8
'''

🏆走迷宫Ⅲ⭐

🚀传送锚点

💡思路点拨

下面来到验证题，主要检测上一题的掌握情况~

自己先做一下，学会了上一题很简单，换汤不换药，改改参数就AC了~

🍞代码详解

#BFS-走迷宫Ⅲ
from collections import deque
n,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)breakfor i,j in [[1,0],[-1,0],[0,1],[0,-1]]:a,b=x+i,y+jif 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

🏆全球变暖⭐⭐⭐

🚀传送锚点

💡思路点拨

最后一道三星省赛真题，挑战大BOSS了！(╯‵□′)╯嘟嘟炸弹！•••*～●

总体思路：(≧∀≦)ゞ

从问题出发，题目问：“多少个岛屿会被全部淹没？”

先判断全部淹没的条件：当前格子是是'#'，上下左右四个格子都是'.'的岛屿。

基本思路：φ(*￣0￣)

二重循环遍历每一个坐标点，如果遇到岛屿，就进行BFS搜索，满足条件统计相加。

注意细节：(～￣▽￣)～

因为岛屿是一整个连通块，所以要一块一块地遍历。

（岛屿是指连在一起的###，不是单独的一个岛#）

🍞代码详解

#BFS-全球变暖
from collections import deque
n=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 flagq=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+jif vis[a][b]==0 and M[a][b]=='#':vis[a][b]=1     #标记岛屿遍历过了q.append((a,b)) #遍历下一个岛屿
ans=0
for 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
'''