混乱的地铁

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

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

如图所示，地铁站编号依次为1、2、3、4、5，每个地铁站的数字分别为2，4，1，2，3。

可以得出结论：从1号地铁站出发，到达3号地铁站最少要坐一趟地铁。

从1号地铁站出发，到达2号地铁站和4号地铁站至少需要坐两趟地铁。

注意，当从4号地铁站出发时，如果向正方向乘坐2站地铁（4号地铁站上的数字为2）​，会超出地铁站范围，因此无法向正方向乘坐地铁。如果向反方向乘坐2站地铁，会到达目的地2号地铁站。如果按照从1号地铁站出发，到达3号地铁站，再到达4号地铁站，最终到达2号地铁站的话需要乘坐3趟地铁，没有上一种地铁乘坐方案便利，应当淘汰这种方案。

使用队列数据结构的广度优先搜索算法，最优的方案一定比次优的方案先进入队列中。

因为广度优先搜索算法具有层次性，每一次遍历距离最近或距离相同的目标。如果距离近是问题答案最重要的考察因素，则广度优先搜索算法会自动地优先搜索距离较近的目标，最快地找到问题的答案。所以，只需建立一个数组或列表来记录是否已经遍历过一个目标，防止重复遍历同一目标导致无限循环即可，不需再担心最优的答案可能出现在重复的遍历过程中。

代码：

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)])  # 输出答案

输入：

图示

输出

这里也可以尝试一下深度优先

station = [-1 for i in range(0, int(num) + 1)]  # station 列表存从出发点到对应地铁站需乘坐地铁的趟数，-1代表无法到达
station[int(start)] = 0  # 出发点到自身地铁站时不用乘坐任何地铁，赋值为0
# 深度优先搜索算法
visited = set()  # 为了区分点是否已被访问，初值为False
s = [int(start)]
while s:
    u = s.pop()
    left = u - int(move[u - 1])  # 计算出向反方向乘坐会到达哪个地铁站
    right = u + int(move[u - 1])  # 计算出向正方向乘坐会到达哪个地铁站
    if u not in visited:
        print(u, " ", end="")
        visited.add(u)
        if left >= 1 and station[left] == -1:  # 如果反方向乘坐没有出界且没有到过，则将新到达的地铁站加入队列
            s.append(left)
            station[left] = station[u] + 1  # 更新到达对应地铁站需乘坐的趟数
        if right <= int(num) and station[right] == -1:  # 如果反方向乘坐没有出界且没有到过，则将新到达的地铁站加入队列
            s.append(right)
            station[right] = station[u] + 1  # 更新到达对应地铁站需乘坐的趟数
print()
print(station[int(end)])  # 输出答案

结果