Comment utiliser la recherche en largeur en Python pour traverser le métro chaotique

Problème de métro chaotique

[Description du problème]

Le réseau de métro dans une certaine ville est extrêmement chaotique. Il y a n stations de métro sur une ligne de métro, numérotées de 1 à n. Il y a une station de métro à chaque station de la ligne de métro. Il y a un nombre m sur chaque station de métro, qui représente le nombre d'arrêts que les passagers doivent emprunter depuis cette station. Chaque station de métro dispose de lignes de métro allant dans les deux sens. Par conséquent, vous pouvez avancer de m stations dans la direction portant un numéro plus grand, ou vous pouvez avancer de m stations dans la direction portant un numéro plus petit. Cependant, si vous dépassez le cadre d’une station de métro, vous ne pouvez pas prendre le métro. Par exemple, le numéro 1 du métro est le 3. Si vous montez dans le train à cette station de métro, vous pouvez vous asseoir en direction avant jusqu'à la station de métro n° 4. Mais vous ne pouvez pas prendre le bus dans la direction opposée à la station de métro -2, car la station de métro -2 n'existe pas. Maintenant, un passager part de la station de métro A et souhaite atteindre la station de métro B. Peut-il l'atteindre au moins ? De combien de trajets en métro a-t-il besoin ?

[Formulaire de saisie]

• Entrez le nombre de stations de métro sur la première ligne

• Entrez le numéro de chaque station de métro en séquence sur la deuxième ligne, séparées par des espaces

• Entrez la station de métro sur la troisième ligne A et B, séparées par des espaces

[Formulaire de sortie]

Nombre minimum de trajets en métro de la station de métro A à B

[Exemple de saisie]

5

2 4 1 2 3

1 2

[Exemple de sortie]

2

Programmation

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

Résumé

Le parcours de recherche en largeur d'abord est principalement implémenté via une file d'attente. Le format spécifique est :

Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

Mettez le premier élément en premier Put. dans la file d'attente, puis retirez le premier élément, trouvez tous les éléments légaux et mettez-les dans la file d'attente, puis retirez-les de la file d'attente un par un jusqu'à ce que la file d'attente soit vide, ce qui signifie que tous les éléments légaux ont été parcourus .

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!