Python怎么使用廣度優先搜索遍歷混亂地鐵

這篇文章主要介紹“Python怎么使用廣度優先搜索遍歷混亂地鐵”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“Python怎么使用廣度優先搜索遍歷混亂地鐵”文章能幫助大家解決問題。

混亂地鐵問題

【問題描述】

在某個城市中地鐵網極度混亂。一條地鐵線路上有n個地鐵站，分別編號為1到n。地鐵線路上的每一個站都會?？康罔F，每一個地鐵站上都有一個數字m，代表從此站出發乘客必須乘坐的站數。每個地鐵站都有通往兩個方向的地鐵。因此可以向編號大的方向前進m站，也可以向編號小的方向前進m站。但如果前進后超出了地鐵站的范圍，則該地鐵不可被乘坐。例如編號為1的地鐵上的數字為3，那么在該地鐵站上車，可以向正方向坐到4號地鐵站。但不能反方向坐車到-2號地鐵站，因為-2號地鐵站不存在?，F在乘客從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怎么使用廣度優先搜索遍歷混亂地鐵”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。