Python使用广度优先搜索遍历混乱地铁问题
混乱地铁问题
【问题描述】
在某个城市中地铁网极度混乱。一条地铁线路上有n个地铁站，分别编号为1到n。地铁线路上的每一个站都会停靠地铁，每一个地铁站上都有一个数字m，代表从此站出发乘客必须乘坐的站数。每个地铁站都有通往两个方向的地铁。因此可以向编号大的方向前进m站，也可以向编号小的方向前进m站。但如果前进后超出了地铁站的范围，则该地铁不可被乘坐。例如编号为1的地铁上的数字为3，那么在该地铁站上车，可以向正方向坐到4号地铁站。但不能反方向坐车到-2号地铁站，因为-2号地铁站不存在。现在乘客从A号地铁站出发，想要到达B号地铁站，求他能否到达，最少要搭乘多少次地铁？
【输入形式】
- 第一行输入地铁站的个数
- 第二行依次输入每个地铁站的数字，以空格隔开
- 第三行输入地铁站A和B，以空格隔开
【输出形式】
地铁站A到B最少要搭乘地铁的次数
【样例输入】
5
2 4 1 2 3
1 2
【样例输出】
2
程序设计
n=int(input())
lst1=[int(i) for i in range(n)]
lst2=list(map(int,input().split()))
start,end=map(int,input().split())
def BFS(lst1,lst2,start,end): #广度优先搜索遍历
count=0 #计算达到终点所需乘坐地铁的次数
visited=[0 for i in range(n)] #设置标志列表
Queue=[] #设置队列，用于广度优先搜索遍历
Queue.append(start-1) #将起点放入队列
flag=1 #用于改变方向
while Queue: #开始循环遍历
t=Queue.pop(0) #出队
for i in range(2): #分别向左右两个方向走
flag=-1*flag #改变方向
new=lst1[t]+flag*lst2[t] #到达的新的地铁站的下标
if new<0 or new>=n: #检查是否合法
continue
if new>=0 or new<n:
Queue.append(new) #若合法，就放入队列中
visited[new]=1 #标记一下
count+=1 #乘坐的地铁次数
if visited[end-1]==1: #如果终点被标记了，说明已经到终点了
return count
return 0
print(BFS(lst1,lst2,start,end)) 总结
广度优先搜索遍历主要通过一个队列来实现，具体的格式为：
Queen.append()
while Queen:
t=Queen.pop()
if ……
Queen.append()先将第一个元素放入队列中，然后将第一个元素取出，并找到合法的所有元素放入队列中，再挨个从队列中取出，直到队列为空，表示所有合法的元素都已经被遍历过了。
到此这篇关于python使用广度优先搜索遍历混乱地铁问题的文章就介绍到这了,更多相关Python广度优先搜索遍历混乱地铁内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
相关文章