So nutzen Sie die Breitensuche in Python, um die chaotische U-Bahn zu durchqueren

Chaos-U-Bahn-Problem

[Problembeschreibung]

In gewisser Weise Das U-Bahn-Netz der Stadt ist äußerst chaotisch. Es gibt n U-Bahn-Stationen auf einer U-Bahn-Linie, nummeriert von 1 bis n. An jeder Station der U-Bahnlinie gibt es eine U-Bahn-Haltestelle. An jeder U-Bahn-Station gibt es eine Zahl m, die die Anzahl der Haltestellen angibt, die Fahrgäste von dieser Station aus nehmen müssen. An jeder U-Bahnstation gibt es U-Bahnlinien, die in beide Richtungen fahren. Daher können Sie m Stationen mit einer größeren Zahl in der Richtung vorrücken, oder Sie können m Stationen mit einer kleineren Zahl in der Richtung vorrücken. Wenn Sie jedoch über den Rahmen einer U-Bahn-Station hinausgehen, können Sie nicht mit der U-Bahn fahren. Die Nummer in der U-Bahn mit der Nummer 1 ist beispielsweise 3. Wenn Sie an dieser U-Bahn-Station in den Zug einsteigen, können Sie in Vorwärtsrichtung zur U-Bahn-Station Nr. 4 sitzen. Sie können jedoch nicht mit dem Bus in die entgegengesetzte Richtung zur U-Bahn-Station -2 fahren, da die U-Bahn-Station -2 nicht existiert. Nun startet ein Fahrgast von der U-Bahn-Station A und möchte die U-Bahn-Station B erreichen. Wie viele U-Bahn-Fahrten benötigt er mindestens?

[Eingabeformular]

• Geben Sie in der ersten Zeile die Anzahl der U-Bahn-Stationen ein

# 🎜🎜#
• Geben Sie in der zweiten Zeile die Nummern der einzelnen U-Bahn-Stationen der Reihe nach ein, getrennt durch Leerzeichen.

• Geben Sie in der dritten Zeile die U-Bahn-Stationen ein A und B, mit Trennung durch Leerzeichen

[Ausgabeformat]

Mindestanzahl der U-Bahn-Fahrten von U-Bahn-Station A nach B

[Beispieleingabe]

5

2 4 1 2 3

1 2

#🎜 🎜## 🎜🎜#【Beispielausgabe】

2

Programmierung

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))

Zusammenfassung. #🎜🎜 # # 🎜🎜#Breadth-First-Suchdurchquerung wird hauptsächlich über eine Warteschlange implementiert. Das spezifische Format ist:

Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

Stellen Sie zuerst das erste Element in die Warteschlange, nehmen Sie dann das erste Element heraus und suchen Sie das legale Alle Elemente werden in die Warteschlange gestellt und dann einzeln aus der Warteschlange entnommen, bis die Warteschlange leer ist, was anzeigt, dass alle zulässigen Elemente durchlaufen wurden.

Das obige ist der detaillierte Inhalt vonSo nutzen Sie die Breitensuche in Python, um die chaotische U-Bahn zu durchqueren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!