模板

BFS，其英文全称是Breadth First Search，中文叫广度优先搜索，从根节点开始遍历，然后遍历根节点的子节点，所有子节点访问到后再遍历子节点的子节点，也就是根据深度每一层每一层的遍历。一般会用到队列和字典这两种数据结构。队列用于存储枚举的节点集合，字典用于记录节点是否访问过，用于排重。

对于一般的迷宫类谜题来说，该算法可以枚举所有的路径，由于它是按层序遍历的，所以当到达终点时，它得到的路径一定是最短的，这也是该算法奏效的原因。

现在的问题的关键就是如何将节点的子节点抽象出来，也就是说从一个状态可以衍生出的所有状态。我们用children函数来表示这个过程，这个函数接收一个输入，得到一个集合。从数据结构上看，是指返回某个节点的所有子节点集合，从现实问题来看，是指从一个状态，只进行最简化（不可拆分）的一步操作能到达的所有状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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表示。
注意这里的一维空间和二维空间互转，索引发生的变化。

1
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
32
33
34
35
36
37
38
39
40
41
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抽离成一个函数：

1
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
   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函数，基本上可完全套用模板。

1
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
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解法：

1
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
32
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)%10) +s[i+1:]  #向上拨动一格 +1，加10再模10，循环拨动并防止数组越界
                yield s[:i]+ str((int(s[i])+9)%10) +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方法解决：

  1. 从一个状态可以延续到其他状态；
  2. 求从起始状态到达目标状态的最少步骤（最短路径）。

其他谜题

在以下谜题中，均采用单向bfs模板，实现的children函数为解题的核心精髓，可供参考。

中等：909. 蛇梯棋
参考答案：

1
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
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. 单词接龙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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. 青蛙过河
参考答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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. 公交路线
参考答案：

1
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
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