How to use breadth-first search in Python to traverse the chaotic subway

Chaotic subway problem

[Problem description]

The subway network in a certain city is extremely chaotic. There are n subway stations on a subway line, numbered 1 to n. There are subway stops at every station on the subway line. There is a number m on each subway station, which represents the number of stops that passengers must take from this station. Every metro station has metro lines going in both directions. Therefore, you can advance m stations in the direction with a larger number, or you can advance m stations in the direction with a smaller number. However, if you go beyond the scope of a subway station, you cannot ride the subway. For example, the number on the subway numbered 1 is 3. If you get on the train at that subway station, you can sit in the forward direction to the No. 4 subway station. But you cannot take the bus in the opposite direction to the -2 subway station, because the -2 subway station does not exist. Now a passenger starts from subway station A and wants to reach subway station B. Can he reach it? How many subway rides do he need at least?

[Input form]

• Enter the number of subway stations in the first line

• The second line in sequence Enter the number of each subway station, separated by spaces

• In the third line, enter subway stations A and B, separated by spaces

[Output format]

Minimum number of subway rides from subway station A to B

[Sample input]

5

2 4 1 2 3

1 2

【Sample output】

2

Programming

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

Summary

Breadth-first search traversal is mainly implemented through a queue. The specific format is:

Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

First put the first element into the queue, and then put the first element Take it out and find all the legal elements and put them into the queue, and then take them out from the queue one by one until the queue is empty, which means that all legal elements have been traversed.

The above is the detailed content of How to use breadth-first search in Python to traverse the chaotic subway. For more information, please follow other related articles on the PHP Chinese website!