Python使用廣度優(yōu)先搜索遍歷混亂地鐵問題
更新時間：2023年04月07日 09:47:04 作者：Want595
這篇文章主要介紹了Python使用廣度優(yōu)先搜索遍歷混亂地鐵問題,廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型,需要的朋友可以參考下
混亂地鐵問題
【問題描述】
在某個城市中地鐵網極度混亂。一條地鐵線路上有n個地鐵站，分別編號為1到n。地鐵線路上的每一個站都會停靠地鐵，每一個地鐵站上都有一個數字m，代表從此站出發(fā)乘客必須乘坐的站數。每個地鐵站都有通往兩個方向的地鐵。因此可以向編號大的方向前進m站，也可以向編號小的方向前進m站。但如果前進后超出了地鐵站的范圍，則該地鐵不可被乘坐。例如編號為1的地鐵上的數字為3，那么在該地鐵站上車，可以向正方向坐到4號地鐵站。但不能反方向坐車到-2號地鐵站，因為-2號地鐵站不存在。現在乘客從A號地鐵站出發(fā)，想要到達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): #廣度優(yōu)先搜索遍歷
count=0 #計算達到終點所需乘坐地鐵的次數
visited=[0 for i in range(n)] #設置標志列表
Queue=[] #設置隊列，用于廣度優(yōu)先搜索遍歷
Queue.append(start-1) #將起點放入隊列
flag=1 #用于改變方向
while Queue: #開始循環(huán)遍歷
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)) 總結
廣度優(yōu)先搜索遍歷主要通過一個隊列來實現，具體的格式為：
Queen.append() while Queen: ? ? t=Queen.pop()? ? ? if …… ? ? ? ? Queen.append()
先將第一個元素放入隊列中，然后將第一個元素取出，并找到合法的所有元素放入隊列中，再挨個從隊列中取出，直到隊列為空，表示所有合法的元素都已經被遍歷過了。
到此這篇關于Python使用廣度優(yōu)先搜索遍歷混亂地鐵問題的文章就介紹到這了,更多相關Python廣度優(yōu)先搜索遍歷混亂地鐵內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了舉例講解Python中is和id的用法,是Python學習當中的基礎知識,作者舉例進行了簡單說明,需要的朋友可以參考下2015-04-04
Python中asyncore異步模塊的用法及實現httpclient的實例
asyncore即是一個異步的socket封裝,特別是dispatcher類中包含了很多異步調用的socket操作方法,非常犀利,下面我們就來講解Python中asyncore異步模塊的用法及實現httpclient的實例2016-06-06
本篇文章主要介紹了tensorflow輸出權重值和偏差的方法，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-02-02
這篇文章主要為大家詳細介紹了python實現簡單的貪吃蛇游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03
Numpy中的ravel_multi_index函數用法說明
這篇文章主要介紹了Numpy中的ravel_multi_index函數用法說明，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05
春聯(lián)是中國傳統(tǒng)文化中最具內涵的元素之一，它以對仗工整、簡潔精巧的文字描繪美好形象，抒發(fā)美好愿望，是中國特有的文學形式，是華人們過年的重要習俗。本文將通過Python制作春聯(lián)，需要的可以參考一下2022-01-01
這篇文章主要和大家介紹一下異常的最后一個知識點——斷言 ，斷言是判斷一個表達式，在表達式為 False 的時候觸發(fā)異常。本文將通過示例詳細介紹一下斷言，需要的可以參考一下2022-03-03
python3格式化字符串 f-string的高級用法(推薦)
從Python 3.6開始，f-string是格式化字符串的一種很好的新方法。與其他格式化方式相比，它們不僅更易讀，更簡潔，不易出錯，而且速度更快！本文重點給大家介紹python3格式化字符串 f-string的高級用法，一起看看吧2020-03-03
這篇文章主要介紹了Python 實現 PS 濾鏡中的徑向模糊特效，幫助大家更好的利用python處理圖片，感興趣的朋友可以了解下2020-12-12
這篇文章主要為大家詳細介紹了如何使用Python完成簡單的PDF文件處理操作，如PDF文件的批量合并、拆分、加密以及添加水印等，需要的可以參考一下2022-09-09