广度优先搜索应用实例—混乱地铁

在某一个城市中地铁网极度混乱。一条地铁线路上有 n 个地铁站,分别编号为 1 到 n。地铁线路上的每一个站都会停靠地铁,每一个地铁站上都有一个数字 m,代表从此站出发乘客必须乘坐的站数。

每个地铁站都有通往两个方向的地铁。因此既可以向编号大的方向前进 m 站,也可以向编号小的方向前进 m 站。但如果前进后超出了地铁站的范围,则该地铁不可被乘坐。例如编号为 1 的地铁上的数字为 3,那么在该地铁站上车,可以向正方向坐车到 4 号地铁站。但不能反方向坐车到 -2 号地铁站,因为 -2 号地铁站不存在。现在乘客从 A 号地铁站出发,想要到达 B 号地铁站,求他能否到达,最少要搭乘多少次地铁?

在分析这个问题前先举一个具体的例子。如图 1 所示,如果一共有 5 个地铁站,其编号依次为 1,2,3,4,5。而每个地铁站的数字分别为 2,4,1,2,3。现在我们来分析乘客从 1 号地铁站上车,想要到达 2 号地铁站的情况。
地铁站及其数字示例
图 1:地铁站及其数字示例

如果乘客从 1 号地铁站出发,则他有两个选择,向正方向坐车,或向反方向坐车。1 号车站的数字为 2,因此可以到达 3 号地铁站和 -1 号地铁站。又因为 -1 号地铁站并不存在,所以从 1 号地铁站出发只能到达 3 号地铁站。综上我们可以得出结论:从 1 号地铁站出发,到达 3 号地铁站最少要坐一趟地铁,如图 2 所示。
地铁站乘坐步骤(1)
图 2:地铁站乘坐步骤(1)

此时到达 3 号地铁站。3 号地铁站的数字为 1,因此可以向正方向坐 1 站车到达 4 号地铁站,也可以向反方向坐 1 站车直接到达目的地 2 号地铁站。同样我们也可以得出结论:从 1 号地铁站出发,到达 2 号地铁站和 4 号地铁站至少需要坐两趟地铁,如图 3 所示。
地铁站乘坐步骤(2)
图 3:地铁站乘坐步骤(2)

此时我们已经遍历出结果:从 1 号地铁站出发到达 2 号地铁站至少要乘坐两次地铁。如果我们的循环跳出条件设立的是到达目的地或队列为空,那么遍历已经结束。但是如果我们的循环跳出条件只有队列为空,那么我们还需进一步遍历,因为此时队列中仍有两个元素:4 号地铁站和 2 号地铁站。

值得注意的是,当我们从 4 号地铁站出发时,如果向正方向乘坐 2 站地铁(4 号地铁站上的数字为 2),将超出地铁站范围,因此无法向正方向乘坐地铁。如果向反方向乘坐 2 站地铁,将会到达目的地 2 号地铁站。当我们按照从 1 号地铁站出发,到达 3 号地铁站,再到达 4 号地铁站,最终到达 2 号地铁站的话需要乘坐 3 趟地铁,没有上一种地铁乘坐方案便利,应当淘汰这种方案,如图 4 所示。
地铁站乘坐步骤(3)
图 4:地铁站乘坐步骤(3)

但如果仔细思考使用队列数据结构的广度优先搜索算法,不难推导出最优的方案一定比次优的方案先进入队列中。因为广度优先搜索算法具有层次性,每一次遍历距离最近或距离相同的目标。如果距离近是问题答案最重要的考察因素,则广度优先搜索算法会自动地优先搜索距离较近的目标,最快地找到问题的答案。

所以,我们只需建立一个数组或列表来记录是否已经遍历过一个目标,防止重复遍历同一目标导致无限循环即可,不需再担心最优的答案可能出现在重复的遍历过程中。

依旧使用广度优先搜索算法的模板,我们在一个 while 循环内对队列结构进行遍历操作,循环的跳出条件依旧为队列为空。

题目代码如下:
#混乱地铁
from queue import Queue        #调用队列库
move = []               #move列表里存储每一个地铁站的数字
Q = Queue()              #建立队列
start, end, num = input().split()    #读入出发点、目的地、总共的地铁站数量
move = input().split()         #读入每个地铁站的数字
station = [-1 for i in range(0, int(num) + 1)]  #station 列表存从出发点到对应地铁站需乘坐地铁的趟数,-1代表无法到达
    Q.put(int(start))                #将出发点放入队列中
station[int(start)] = 0             #出发点到自身地铁站时不用乘坐任何地铁,赋值为0
while not Q.empty():              #广度优先搜索循环
    cur = Q.get()                #取出队列第一项,并将其移出队列
    left = cur - int(move[cur - 1])       #计算出向反方向乘坐会到达哪个地铁站
    right = cur + int(move[cur - 1])       #计算出向正方向乘坐会到达哪个地铁站
    if left >= 1 and station[left] == -1:    #如果反方向乘坐没有出界且没有到过,则将新到达的地铁站加入队列
        Q.put(left)
        station[left] = station[cur] + 1       #更新到达对应地铁站需乘坐的趟数
    if right <= int(num) and station[right] == -1:  #如果反方向乘坐没有出界且没有到过,则将新到达的地铁站加入队列
        Q.put(right)
        station[right] = station[cur] + 1     #更新到达对应地铁站需乘坐的趟数
print(station[int(end)])            #输出答案