Python使用廣度優(yōu)先搜索遍歷混亂地鐵問題
混亂地鐵問題
【問題描述】
在某個(gè)城市中地鐵網(wǎng)極度混亂。一條地鐵線路上有n個(gè)地鐵站，分別編號(hào)為1到n。地鐵線路上的每一個(gè)站都會(huì)停靠地鐵，每一個(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)地鐵站不存在。現(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中is和id的用法,是Python學(xué)習(xí)當(dāng)中的基礎(chǔ)知識(shí),作者舉例進(jìn)行了簡(jiǎn)單說明,需要的朋友可以參考下2015-04-04
Python中asyncore異步模塊的用法及實(shí)現(xiàn)httpclient的實(shí)例
asyncore即是一個(gè)異步的socket封裝,特別是dispatcher類中包含了很多異步調(diào)用的socket操作方法,非常犀利,下面我們就來講解Python中asyncore異步模塊的用法及實(shí)現(xiàn)httpclient的實(shí)例2016-06-06
本篇文章主要介紹了tensorflow輸出權(quán)重值和偏差的方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-02-02
python實(shí)現(xiàn)簡(jiǎn)單的貪吃蛇游戲
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)簡(jiǎn)單的貪吃蛇游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-03-03
Numpy中的ravel_multi_index函數(shù)用法說明
這篇文章主要介紹了Numpy中的ravel_multi_index函數(shù)用法說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-05-05
春聯(lián)是中國(guó)傳統(tǒng)文化中最具內(nèi)涵的元素之一，它以對(duì)仗工整、簡(jiǎn)潔精巧的文字描繪美好形象，抒發(fā)美好愿望，是中國(guó)特有的文學(xué)形式，是華人們過年的重要習(xí)俗。本文將通過Python制作春聯(lián)，需要的可以參考一下2022-01-01
這篇文章主要和大家介紹一下異常的最后一個(gè)知識(shí)點(diǎn)——斷言 ，斷言是判斷一個(gè)表達(dá)式，在表達(dá)式為 False 的時(shí)候觸發(fā)異常。本文將通過示例詳細(xì)介紹一下斷言，需要的可以參考一下2022-03-03
python3格式化字符串 f-string的高級(jí)用法(推薦)
從Python 3.6開始，f-string是格式化字符串的一種很好的新方法。與其他格式化方式相比，它們不僅更易讀，更簡(jiǎn)潔，不易出錯(cuò)，而且速度更快！本文重點(diǎn)給大家介紹python3格式化字符串 f-string的高級(jí)用法，一起看看吧2020-03-03
Python 實(shí)現(xiàn)PS濾鏡中的徑向模糊特效
這篇文章主要介紹了Python 實(shí)現(xiàn) PS 濾鏡中的徑向模糊特效，幫助大家更好的利用python處理圖片，感興趣的朋友可以了解下2020-12-12
Python實(shí)現(xiàn)自動(dòng)化處理PDF文件的方法詳解
這篇文章主要為大家詳細(xì)介紹了如何使用Python完成簡(jiǎn)單的PDF文件處理操作，如PDF文件的批量合并、拆分、加密以及添加水印等，需要的可以參考一下2022-09-09