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怎麼用廣度優先搜尋遍歷混亂地鐵的詳細內容。更多資訊請關注PHP中文網其他相關文章！