Confusing subway issues
[Problem description]
The subway network in a certain city is extremely confusing. There are n subway stations on a subway line, numbered 1 through n. Each station on the subway line stops the subway, and each subway station is marked with the number m, which represents the number of stops a passenger must take from that station. Each subway station has subways going in both directions. Thus it is possible to go forward m stations in the direction with the larger number, or m stations in the direction with the smaller number. However, if you go beyond the boundaries of a subway station, the subway cannot be used. For example, if a subway numbered 1 has the number 3 on it, then you can get on the train at that subway station and ride in the positive direction to subway station 4. But one cannot ride in the opposite direction to subway station -2 because subway station -2 does not exist. Now a passenger is traveling from metro station A and wants to reach metro station B. Find whether he can reach it or not and what is the minimum number of metro rides he has to take?
[Input Form]
- Enter the number of subway stations in the first line
- On the second line, enter the number of each subway station in turn, separated by spaces
- Enter subway stations A and B on the third line, separated by spaces
[Form of output]
Minimum number of subway rides from subway station A to B
[Sample Input]
5
2 4 1 2 3
1 2
[Sample Output]
2
computer 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): # Breadth-first search traversal
count=0 # Calculate the number of subway rides required to reach the end point
visited=[0 for i in range(n)] #Set the list of flags
Queue=[] # Set up a queue for breadth-first search traversal
(start-1) # Put the starting point in the queue
flag=1 # For change of direction
while Queue: # Start the loop traversal
t=(0) # Out of the line
for i in range(2): # Going in both directions
flag=-1*flag # Change of direction
new=lst1[t]+flag*lst2[t] #Subscripts of new subway stations to be reached
if new<0 or new>=n: #Check if it's legal
continue
if new>=0 or new<n:
(new) # If it's legal, put it in the queue
visited[new]=1 # Mark it up
count+=1 # of subway rides
if visited[end-1]==1: # If the end is marked, it means it's at the end #
return count
return 0
print(BFS(lst1,lst2,start,end)) summarize
The breadth-first search traversal is mainly implemented through a queue in the format:
() while Queen: t=() if …… ()
First put the first element into the queue, then take the first element out and find all the legal elements to put into the queue, then take them out of the queue one by one until the queue is empty, indicating that all the legal elements have been traversed.
To this article on the use of Python breadth-first search traversal of the chaotic subway problem is introduced to this article, more related Python breadth-first search traversal of the chaotic subway content, please search for my previous articles or continue to browse the following related articles I hope that you will have more support for me in the future!