Python怎么使用廣度優(yōu)先搜索遍歷混亂地鐵

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

混亂地鐵問題

【問題描述】

在某個(gè)城市中地鐵網(wǎng)極度混亂。一條地鐵線路上有n個(gè)地鐵站，分別編號為1到n。地鐵線路上的每一個(gè)站都會?？康罔F，每一個(gè)地鐵站上都有一個(gè)數(shù)字m，代表從此站出發(fā)乘客必須乘坐的站數(shù)。每個(gè)地鐵站都有通往兩個(gè)方向的地鐵。因此可以向編號大的方向前進(jìn)m站，也可以向編號小的方向前進(jìn)m站。但如果前進(jìn)后超出了地鐵站的范圍，則該地鐵不可被乘坐。例如編號為1的地鐵上的數(shù)字為3，那么在該地鐵站上車，可以向正方向坐到4號地鐵站。但不能反方向坐車到-2號地鐵站，因?yàn)?2號地鐵站不存在?，F(xiàn)在乘客從A號地鐵站出發(fā)，想要到達(dá)B號地鐵站，求他能否到達(dá)，最少要搭乘多少次地鐵？

【輸入形式】

• 第一行輸入地鐵站的個(gè)數(shù)

• 第二行依次輸入每個(gè)地鐵站的數(shù)字，以空格隔開

• 第三行輸入地鐵站A和B，以空格隔開

【輸出形式】

地鐵站A到B最少要搭乘地鐵的次數(shù)

【樣例輸入】

5

2 4 1 2 3

1 2 

【樣例輸出】

2

程序設(shè)計(jì) 

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):      #廣度優(yōu)先搜索遍歷
    count=0          #計(jì)算達(dá)到終點(diǎn)所需乘坐地鐵的次數(shù)
    visited=[0 for i in range(n)]    #設(shè)置標(biāo)志列表
    Queue=[]         #設(shè)置隊(duì)列，用于廣度優(yōu)先搜索遍歷
    Queue.append(start-1)   #將起點(diǎn)放入隊(duì)列
    flag=1           #用于改變方向
    while Queue:    #開始循環(huán)遍歷
        t=Queue.pop(0)   #出隊(duì)
        for i in range(2):    #分別向左右兩個(gè)方向走
            flag=-1*flag    #改變方向       
            new=lst1[t]+flag*lst2[t]    #到達(dá)的新的地鐵站的下標(biāo)
            if new<0 or new>=n:      #檢查是否合法
                continue 
            if new>=0 or new<n:
                Queue.append(new)     #若合法，就放入隊(duì)列中
                visited[new]=1        #標(biāo)記一下
                count+=1              #乘坐的地鐵次數(shù)
                if visited[end-1]==1:   #如果終點(diǎn)被標(biāo)記了，說明已經(jīng)到終點(diǎn)了
                    return count
    return 0
print(BFS(lst1,lst2,start,end))

總結(jié) 

廣度優(yōu)先搜索遍歷主要通過一個(gè)隊(duì)列來實(shí)現(xiàn)，具體的格式為：

Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

先將第一個(gè)元素放入隊(duì)列中，然后將第一個(gè)元素取出，并找到合法的所有元素放入隊(duì)列中，再挨個(gè)從隊(duì)列中取出，直到隊(duì)列為空，表示所有合法的元素都已經(jīng)被遍歷過了。

關(guān)于“Python怎么使用廣度優(yōu)先搜索遍歷混亂地鐵”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。