Python で幅優先検索を使用して混沌とした地下鉄を横断する方法

混沌とした地下鉄問題

[問題の説明]

ある都市の地下鉄網は非常に混沌としています。地下鉄路線には n 個の地下鉄駅があり、1 から n まで番号が付けられています。地下鉄の各駅には地下鉄の停留所があり、各駅にはその駅から何番目の停留所に乗らなければならないかを表す m という数字が付いています。どの地下鉄駅にも地下鉄が両方向に通っています。したがって、数字の大きい方向に m 駅進めることもできますし、数字の小さい方向に m 駅進めることもできます。ただし、地下鉄の駅の範囲を越えると地下鉄には乗れません。たとえば、地下鉄 1 番の駅の番号は 3 です。その地下鉄の駅から電車に乗ると、地下鉄 4 番の駅の進行方向に座ることができます。ただし、地下鉄 -2 駅は存在しないため、地下鉄 -2 駅と逆方向のバスには乗車できません。今、乗客は地下鉄 A 駅から出発し、地下鉄 B 駅に行きたいと考えています。彼はそこに到着できますか? 少なくとも何回地下鉄に乗る必要がありますか?

[入力フォーム]

• 1行目に地下鉄の駅番号を入力

• 2行目地下鉄の各駅の番号をスペースで区切って順番に入力

• 3行目に地下鉄の駅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()

最初に最初の要素をキューに入れ、次に最初の要素を取り出します。そして、すべての正当な要素を見つけてキューに入れ、キューが空になるまでキューから 1 つずつ取り出します。これは、すべての正当な要素が走査されたことを意味します。

以上がPython で幅優先検索を使用して混沌とした地下鉄を横断する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。