广度优先搜索应用实例—艰难旅行

现已知一个大小为 N · M 的地图,地图中只有可能出现两个数字:0 或 1,现规定如果位于数字为 0 的格子上,则下一步只能往相邻四个格子中数字为 1 的格子走,如果位于数字为 1 的格子上,则下一步只能往相邻四个格子中数字为 0 的格子走。如果给定起点格子,则可以向上下左右四个方向移动,且同一个格子不能重复走,求能在地图中到达多少格子?

如图 1 和图 2 所示,假设地图为一个方格图,且给定的起点为左上角灰色的方格。
地图示例(1)
图 1:地图示例(1)

地图示例(2)
图 2:地图示例(2)

如图 1 所示,从左上角的格子出发,可以从 1,到达右边与下方的 0,再到达右边与下方的 1,从而到达地图上的所有方格。因此,图 1 所示的地图可以求解出的答案应为 25,即可以到达图上的所有方格。而对于图 2 而言,仍从左上角灰色的格子出发,我们会发现其右边和下方的方格均为 1,因此无法移动到任何其他方格中,求解出能到达的格子数为 1。

分析完上面两个基础例子,就会自然地想到广度优先搜索算法或许能解决这个问题。广度优先搜索算法的核心思想是队列,我们先创建一个队列结构。因为广度优先搜索算法优先搜索离起始点最近的点,所以可以通过判断现在位于的方格的上下左右四个方格是否能到达来构建队列。

如果可以到达,则加入队列的末尾,如果不能到达则跳过。以这种方式来更新队列,可以保证每一种移动方案均能被考虑到。而为了不重复遍历相同的路径,我们需用一个列表来存储一个格子是否被加入队列过,防止浪费计算资源。

假设一个地图如图 3 所示(外围的数字为行列标号),并且起点为第三行第三列的灰色格子。现创建一个队列结构,并将起点加入队列中,完成初始化(队列中的格子均用行列标号表示,如第一行第二列的方格表示为 (1,2))。队列的状态如图 4 所示。
地图示例(3)
图 3:地图示例(3)
例题队列操作(1)
图 4:例题队列操作(1)

此时判断所在方格位置的周围四个方格是否可以到达。(3,3) 位置的方格中的数字为 0,其上下左右的四个方格的数字均为 1,因此其上下左右的方格均能到达。在这个过程中,值得注意的是在这个步骤结束后,需将现所位于的方格移出队列(其实也可以在判断四周方格之前就移出,并不影响最终结果)。同时需记录已进入过队列的方格,防止其再次进入队列。

实行上述步骤时队列的状态如图 5 和图 6 所示。
例题队列操作(2)
图 5:例题队列操作(2)
例题队列操作(3)
图 6:例题队列操作(3)

在进行上述操作过后,方格 (3,3) 被移出队列,而 (2,3) (4,3) (3,2) (3,4) 从队尾加入队列。需要注意的是,将并列元素加入队列时,其加入的顺序并不关键,因为无论先后,这些元素都会被移出队列进行进一步的遍历和判断,而其被移出的顺序也只会影响遍历的顺序而并不会影响结果。

这时我们只需重复之前的步骤,将队列中最前面的方格移出队列,并将从该方格出发可以到达的四周方格加入队列即可。我们将 (2,3) 移出队列,然后将从 (2,3) 出发可以到达的点 (2,4)  (2,2) 加入队列。继续将队列首项 (4,3) 移出,加入 (4,2),如图 7~图 9 所示。
例题队列操作(4)
图 7:例题队列操作(4)

例题队列操作(5)
图 8:例题队列操作(5)
例题队列操作(6)
图 9:例题队列操作(6)

这时我们继续将队首的方格移出队列。从方格 (3,2) 出发,根据地图我们可以推断出有三个相邻方格可以到达 (2,2) (3,1) (4,2)。然而方格 (2,2) (4,2) 已经在队列中,因此不再加入队列,避免重复遍历。这次操作中只有方格 (3,1) 加入队列。

根据上述操作规则如此反复,直到队列为空为止,即可求得本题的答案。最终结果如图 10 所示,所有灰色的方格均可以从起始点 (3,3 )到达,一共可以到达 11 个方格。
地图搜索结果
图 10:地图搜索结果

通过上面的几个例子可知,很显然队列的操作是广度优先搜索算法的核心。因为广度优先搜索算法不像深度优先搜索算法,有特定的循环遍历跳出条件,所以广度优先搜索算法往往以队列为空作为唯一的跳出循环遍历的条件。

同时,我们用 while 循环来进行广度优先搜索,因为 while 此时会比 for 循环更加简洁:
Q = Queue()      #建立队列结构
Q.put(…)       #队列的初始化,往往将起始的元素加入队列
while not Q.empty(): #判断队列是否为空,如果为空,则停止循环
    cur = Q.get()   #访问队列中第一个元素,同时将其移出队列
    …
        Q.put(…)     #将这一步遍历出来的结果加入队列

以上便是广度优先搜索代码的基本模板。我们先调用 Python 自带的 queue 库引入队列,并建立队列结构,之后初始化队列,将起始的元素(如出发点,出发的方格)加入队列。之后便开始遍历。

while 循环的循环条件为队列不为空,如果队列为空,说明广度优先搜索算法已经遍历完毕,可以跳出循环。while 循环中,我们往往会先提取出队列的一个元素(或前几位元素,因题目而定),从提取出的元素入手,开始遍历。经过一系列操作和遍历条件的判断后,需将这一步遍历的结果加入到队列中,等待在之后的遍历中取出。

对于本题而言,额外需要考虑的条件只有相邻的格子中数字不相同时才能到达,以及越界情况(遍历出地图之外)。所以我们只需在 while 循环中加入这些判断语句,广度优先搜索的大致功能就已经完成了。

针对本题的题目设定,我们只能向上下左右移动一个单位。为了简便书写,我们不会使用四个判断语句来完成四个方向的移动,而是定义两个列表,分别存储 x 方向和 y 方向的移动。例如,x 方向的列表为 [0,1,0,-1],y 方向的列表为 [1,0,-1,0],如此只需要一个 for 循环,其中 x[i],y[i] 分别代表不同方向的移动情况,就能完成上下左右四个方向的遍历(x=0,y=1 为向上,x=1,y=0 为向右,x=0, y=-1 为向下,x=-1,y=0 为向左)。

完整代码如下:
# 艰难旅行
from queue import Queue
Q = Queue()          #建立队列
class grid:          #定义grid类,其中每一个方格(grid)都含有行(row)和列(col)属性
    def __init__(self, row, col):
        self.row = row
        self.col = col
    def bfs(self,val,startrow,startcol):
        row = len(val)     #val是存储地图的二位列表,row变量为其行数
        col = len(val[0])    #col变量为地图的列数
    arrived = [[False for j in range(int(col))] for i in range(int(row))]
    #arrived二维列表存储地图上每个方格是否已经到达过(已经进入过队列)
    moverow = [0, 1, 0, -1]
    #moverow数组存储向相邻方格移动时行的变化情况分别为增加1(1),减少1(-1),和不变(0)
    movecol = [1, 0, -1, 0]
    #moverow数组存储向相邻方格移动时列的变化情况,与moverow原理相同
    ans = 1
    Q.put(grid(int(startrow), int(startcol)))       #将起点加入队列
    arrived[int(startrow) - 1][int(startcol) - 1] = True  #将起点设为已到达过
    while not Q.empty():       #判断队列是否为空
        cur = Q.get()        #取出队列首位的元素
        for i in range(4):
        #遍历moverow和movecol,其实就是向现所位于的方格的四个方向的移动
        newrow = cur.row + moverow[i]
        newcol = cur.col + movecol[i]
        if newrow > row or newrow <= 0 or newcol > col or newcol <= 0:
        #判断移动后是否超界
            continue
        if not arrived[newrow - 1][newcol - 1] and val[newrow - 1][newcol - 1] !=val[cur.row - 1][cur.col - 1]:            #判断是否已经到达过,是否与起始点的数值不同
            Q.put(grid(newrow, newcol))   #将发现可以到达的新方格放入队列中
            arrived[newrow - 1][newcol - 1] = True #将可到达的新方格设为已到达过
            ans += 1            #求得答案
    return ans