大家好，我是爱分享的小蓝，欢迎交流指正~ 
全文目录?
?说在前面
?模板-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 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 ?全球变暖⭐⭐⭐
?传送锚点
?思路点拨
最后一道三星省赛真题，挑战大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天，一起冲刺省赛一等奖！
