模板
BFS，其英文全称是Breadth First Search，中文叫广度优先搜索，从根节点开始遍历，然后遍历根节点的子节点，所有子节点访问到后再遍历子节点的子节点，也就是根据深度每一层每一层的遍历。一般会用到队列和字典这两种数据结构。队列用于存储枚举的节点集合，字典用于记录节点是否访问过，用于排重。
对于一般的迷宫类谜题来说，该算法可以枚举所有的路径，由于它是按层序遍历的，所以当到达终点时，它得到的路径一定是最短的，这也是该算法奏效的原因。
现在的问题的关键就是如何将节点的子节点抽象出来，也就是说从一个状态可以衍生出的所有状态。我们用children函数来表示这个过程，这个函数接收一个输入，得到一个集合。从数据结构上看，是指返回某个节点的所有子节点集合，从现实问题来看，是指从一个状态，只进行最简化（不可拆分）的一步操作能到达的所有状态。
12345678910111213141516171819 | def children(status): ...def solution(): start = ... end = ... queue = [(start,0)] #队列：记录节点数据，也记录了节点所在深度 marked = set() #标记字典：用于排除重复 marked.add(start) while queue: s,r = queue.pop(0) #if s == end: #当到达末尾时，此时的深度就是最短路径 # return r for ss in children(s): if ss == end: #优化：可以将判断放在循环中，这样可以少一轮子节点的遍历，但是注意要对结果加1 return r 1 if not ss in marked: queue.append((ss,r 1)) marked.add(ss) return -1 #无路径可达，返回-1 |
|---|
谜题一
来自力扣的困难题：773. 滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示. 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1.
示例：
输入：board = [[1,2,3],[4,0,5]] 输出：1 解释：交换 0 和 5 ，1 步完成 输入：board = [[1,2,3],[5,4,0]] 输出：-1 解释：没有办法完成谜板 输入：board = [[4,1,2],[5,0,3]] 输出：5 解释： 最少完成谜板的最少移动次数是 5 ， 一种移动路径: 尚未移动: [[4,1,2],[5,0,3]] 移动 1 次: [[4,1,2],[0,5,3]] 移动 2 次: [[0,1,2],[4,5,3]] 移动 3 次: [[1,0,2],[4,5,3]] 移动 4 次: [[1,2,0],[4,5,3]] 移动 5 次: [[1,2,3],[4,5,0]]
解答
求能否到达最终状态，并且是最少步骤，标准的BFS思路。我们这里只需要完成children函数即可，在当前棋盘下，移动完一步0后，可以得到的所有状态，0可以上下左右移动（不能超过边界）。
我们需要把棋盘表示成一种状态，我这里用一个一维的tuple表示。
注意这里的一维空间和二维空间互转，索引发生的变化。
1234567891011121314151617181920212223242526272829303132333435363738394041 | class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: def children(status): i=0 while i<len(status): if status[i]==0: #先找到 0 所在位置 break i =1 x,y=i%3,i//3 #一维转二维坐标 #判断能否四个方向的移动 if y>0: #上移 res=list(status) res[i],res[i-3]=res[i-3],res[i] #相当于一维坐标-3，3是二维数组的列长度 yield tuple(res) if y<1: #下移 res=list(status) res[i],res[i 3]=res[i 3],res[i] #相当于一维坐标 3 yield tuple(res) if x>0: #右移 res=list(status) res[i],res[i-1]=res[i-1],res[i] #相当于一维坐标-1 yield tuple(res) if x<2: #左移 res=list(status) res[i],res[i 1]=res[i 1],res[i] #相当于一维坐标 1 yield tuple(res) start=tuple(board[0] board[1]) #起始状态 end=(1,2,3,4,5,0) #结束状态 #下面就是标准的bfs思想了 queue=[(start,0)] marked=set() marked.add(start) while queue: s,r=queue.pop(0) if s==end: return r for ss in children(s): if not ss in marked: queue.append((ss,r 1)) marked.add(ss) return -1 |
|---|
进阶
以上解法是朴素的 BFS 实现，即单向遍历。其存在空间复杂度的瓶颈，由于每次搜索整个层级，空间复杂度可能无比巨大。
还可以采用双向BFS的方式，即设置2个队列，1个队列从开始节点遍历，1个队列从结尾节点遍历，2个队列相向遍历，一旦2个队列发生重合，即某个节点在2个队列中都存在，则说明路径存在。而2个队列谁比较短，我们就遍历谁，以减少搜索空间。我们把单向BFS抽离成一个函数：
123456789101112131415161718192021222324252627282930 | def children(status): ...def bfs(queue,marked,targeted): while queue: s,r = queue.pop(0) #if s in targeted: # return r targeted[s] #双向遍历，当节点在2个队列中都存在时，要累加该节点在2个队列中的深度 for ss in children(s): if ss in targeted: #优化：可以将判断放在循环中，这样可以少一轮子节点的遍历，但是注意要对结果加1 return r 1 targeted[ss] if not ss in marked: queue.append((ss,r 1)) marked[ss] = r 1 return -1 def solution(): start= ... end= ... q1=[(start,0)] #队列1，从开始节点遍历 q2=[(end,0)] #队列2，从结束节点遍历 m1={start:0} #队列1的标记字典，除了标记，还要记录节点深度，用于最后重合时，将2个节点深度累加 m2={end:0} #队列2的标记字典 while q1 and q2: #2个队列都不能为空，其中一个为空，说明永不可能相交 t=-1 if len(q1)>len(q2): #搜索较短的队列 t=bfs(q2,m2,m1) else: t=bfs(q1,m1,m2) if t>=0: return t #一旦搜索到结果，立即返回，否则继续循环。下次循环中2个队列长度发生变化，依然搜索较短的那个 return -1 |
|---|
完整代码，除了children函数，基本上可完全套用模板。
1234567891011121314151617181920212223242526272829 | class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: def children(status): ... 略 def bfs(queue,marked,targeted): while queue: s,r=queue.pop(0) if s in targeted: return r targeted[s] for ss in children(s): if not ss in marked: queue.append((ss,r 1)) marked[ss]=r 1 return -1 start=tuple(board[0] board[1]) end=(1,2,3,4,5,0) q1=[(start,0)] q2=[(end,0)] m1={start:0} m2={end:0} while q1 and q2: t=-1 if len(q1)>len(q2): t=bfs(q2,m2,m1) else: t=bfs(q1,m1,m2) if t>=0: return t return -1 |
|---|
谜题二
普通题：752. 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
双向BFS解法：
1234567891011121314151617181920212223242526272829303132 | class Solution: def openLock(self, deadends: List[str], target: str) -> int: deadends=set(deadends) if '0000' in deadends or target in deadends: return -1 def children(s): for i in range(4): #四个拨轮轮流拨动一次能得到的结果 yield s[:i] str((int(s[i]) 11)) s[i 1:] #向上拨动一格 1，加10再模10，循环拨动并防止数组越界 yield s[:i] str((int(s[i]) 9)) s[i 1:] #向下拨动一格 -1，加10再模10，循环拨动并防止数组越界 def bfs(queue,marked,targeted): while queue: s,r=queue.pop(0) if s in targeted: return r targeted[s] for ss in children(s): if not ss in marked and not ss in deadends: queue.append((ss,r 1)) marked[ss]=r 1 return -1 q1=[('0000',0)] q2=[(target,0)] m1={'0000':0} m2={target:0} while q1 and q2: t=-1 if len(q1)>len(q2): t=bfs(q2,m2,m1) else: t=bfs(q1,m1,m2) if t>=0: return t return -1 |
|---|
可以看到，除了我们需要分析题意，抽象化children方法外，其他都可以完全套用BFS模板。
这类谜题有2个共通点，只要满足这2点，我们都可以采用BFS方法解决：
- 从一个状态可以延续到其他状态；
- 求从起始状态到达目标状态的最少步骤（最短路径）。
其他谜题
在以下谜题中，均采用单向bfs模板，实现的children函数为解题的核心精髓，可供参考。
中等：909. 蛇梯棋 参考答案：
1234567891011121314151617181920212223242526272829 | def snakesAndLadders(self, board: List[List[int]]) -> int: n=len(board) o=(n-1)%2 dic={} for i in range(n-1,-1,-1): for j in range(n): x=(n-i-1)*n (j 1 if i%2==o else n-j) if board[i][j]!=-1: dic[x]=board[i][j] def children(x): for i in range(x 1,min(x 7,end 1)): if i in dic: yield dic[i] else: yield i start=1 end=n*n queue=[(start,0)] marked=set() marked.add(start) while queue: s,r=queue.pop(0) for ss in children(s): if ss == end: return r 1 if not ss in marked: queue.append((ss,r 1)) marked.add(ss) return -1 |
|---|
困难：127. 单词接龙
12345678910111213141516171819202122 | def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: words=set(wordList) if not endWord in words: return 0 def children(word): for i in range(len(word)): for c in range(26): s=word[:i] chr(97 c) word[i 1:] if s!=word and s in words: yield s queue=[(beginWord,1)] marked=set() marked.add(beginWord) while queue: s,r=queue.pop(0) for ss in children(s): if ss==endWord: return r 1 if not ss in marked: queue.append((ss,r 1)) marked.add(ss) return 0 |
|---|
困难：403. 青蛙过河 参考答案：
123456789101112131415161718192021 | def canCross(self, stones: List[int]) -> bool: dic=set(stones) def children(status): s,k=status for k in range(status[1]-1,status[1] 2): if status[0] k in dic: yield (status[0] k,k) start=(0,0) end=stones[-1] queue=[start] marked=set() marked.add(start) while queue: s=queue.pop(0) for ss in children(s): if ss[0]==end: return True if not ss in marked: queue.append(ss) marked.add(ss) return False |
|---|
困难：815. 公交路线 参考答案：
1234567891011121314151617181920212223242526 | def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int: if source==target: return 0 dic={} for i in range(len(routes)): for j in routes[i]: if not j in dic: dic[j]=[] dic[j].append(i) def children(status): yield from routes[status] queue=[] marked=set() for i in dic[source]: queue.append((i,0)) marked.add(i) while queue: s,r=queue.pop(0) for station in children(s): if station==target: return r 1 for bus in dic[station]: if not bus in marked: queue.append((bus,r 1)) marked.add(bus) return -1 |
|---|
