Python使用廣度優(yōu)先搜索遍歷混亂地鐵問題
混亂地鐵問題
【問題描述】
在某個(gè)城市中地鐵網(wǎng)極度混亂。一條地鐵線路上有n個(gè)地鐵站，分別編號(hào)為1到n。地鐵線路上的每一個(gè)站都會(huì)?？康罔F，每一個(gè)地鐵站上都有一個(gè)數(shù)字m，代表從此站出發(fā)乘客必須乘坐的站數(shù)。每個(gè)地鐵站都有通往兩個(gè)方向的地鐵。因此可以向編號(hào)大的方向前進(jìn)m站，也可以向編號(hào)小的方向前進(jìn)m站。但如果前進(jìn)后超出了地鐵站的范圍，則該地鐵不可被乘坐。例如編號(hào)為1的地鐵上的數(shù)字為3，那么在該地鐵站上車，可以向正方向坐到4號(hào)地鐵站。但不能反方向坐車到-2號(hào)地鐵站，因?yàn)?2號(hào)地鐵站不存在?，F(xiàn)在乘客從A號(hào)地鐵站出發(fā)，想要到達(dá)B號(hào)地鐵站，求他能否到達(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)先搜索遍歷混亂地鐵問題的文章就介紹到這了,更多相關(guān)Python廣度優(yōu)先搜索遍歷混亂地鐵內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Python 沒有main函數(shù)的原因，文中講解非常詳細(xì)，示例代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
Python提取特定時(shí)間段內(nèi)數(shù)據(jù)的方法實(shí)例
今天小編就為大家分享一篇關(guān)于Python提取特定時(shí)間段內(nèi)數(shù)據(jù)的方法實(shí)例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-04-04
Python使用pathlib庫(kù)實(shí)現(xiàn)優(yōu)雅的處理路徑
如果你需要在 Python 里進(jìn)行文件處理,那么標(biāo)準(zhǔn)庫(kù)中的os和os.path兄弟倆一定是你無(wú)法避開的兩個(gè)模塊,本文主要來和大家聊聊如何使用pathlib庫(kù)實(shí)現(xiàn)優(yōu)雅的處理路徑,感興趣的可以了解下2023-12-12
Ubuntu22.04安裝PyTorch1.12.1 GPU版本全過程
這篇文章主要介紹了Ubuntu22.04安裝PyTorch1.12.1 GPU版本全過程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
tensorboard是tensorflow用來可視化訓(xùn)練和測(cè)試過程的模塊，而pytorch并沒有可視化模塊，但是pytoch=1.2.0版本以上開始支持tensorboard2022-10-10
Python+AutoIt實(shí)現(xiàn)界面工具開發(fā)過程詳解
這篇文章主要介紹了Python+AutoIt實(shí)現(xiàn)界面工具開發(fā)過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08
pytorch動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò)(擬合)實(shí)現(xiàn)
這篇文章主要介紹了pytorch動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò)(擬合)實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
如何在Python中將字符串轉(zhuǎn)換為數(shù)組詳解
最近在用Python,做一個(gè)小腳本,有個(gè)操作就是要把內(nèi)容換成數(shù)組對(duì)象再進(jìn)行相關(guān)操作,下面這篇文章主要給大家介紹了關(guān)于如何在Python中將字符串轉(zhuǎn)換為數(shù)組的相關(guān)資料,需要的朋友可以參考下2022-12-12
python將一個(gè)英文語(yǔ)句以單詞為單位逆序排放的方法
今天小編就為大家分享一篇python將一個(gè)英文語(yǔ)句以單詞為單位逆序排放的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-12-12
Python爬蟲模擬登陸嗶哩嗶哩(bilibili)并突破點(diǎn)選驗(yàn)證碼功能
這篇文章主要介紹了Python爬蟲模擬登陸嗶哩嗶哩(bilibili)并突破點(diǎn)選驗(yàn)證碼功能,本文通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12