혼란스러운 지하철을 통과하기 위해 Python에서 너비 우선 검색을 사용하는 방법

혼돈의 지하철 문제

[문제 설명]

특정 도시의 지하철망이 극도로 혼란스럽습니다. 지하철 노선에는 1부터 n까지 n개의 지하철역이 있습니다. 지하철 노선의 모든 역에는 지하철역이 있으며, 각 역에는 승객이 이 역에서 거쳐야 하는 정거장 수를 나타내는 숫자 m이 있습니다. 모든 지하철 역에는 양방향으로 가는 지하철 노선이 있습니다. 따라서, m개의 스테이션을 더 큰 숫자 방향으로 전진시킬 수도 있고, m개의 스테이션을 더 작은 숫자의 방향으로 전진시킬 수도 있습니다. 단, 지하철역 범위를 벗어나면 지하철을 탈 수 없습니다. 예를 들어 1번 지하철의 번호는 3번입니다. 해당 역에서 기차를 타면 4번 역 앞쪽에 앉으시면 됩니다. 하지만 -2역이 없기 때문에 반대방향으로는 -2역으로 가는 버스를 탈 수 없습니다. 이제 승객은 지하철 A역에서 출발하여 지하철 B역에 가길 원합니다. 그 승객은 지하철을 최소한 몇 번 타야 합니까?

[입력양식]

• 1호선의 지하철역 번호를 입력하세요

• 2호선의 각 지하철역 번호를 공백으로 구분하여 순차적으로 입력하세요

• 지하철역을 입력하세요 세 번째 라인 A와 B를 공백으로 구분하여

[출력 형식]

역 A에서 B까지 지하철을 타는 최소 횟수

[샘플 입력]

5

2 4 1 2 3

1 2

【샘플 출력】

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

폭 우선 검색 순회는 주로 대기열을 통해 구현됩니다.

Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

첫 번째 요소를 먼저 넣습니다. 그런 다음 첫 번째 요소를 꺼내고 모든 유효한 요소를 찾아서 대기열에 넣은 다음 대기열이 빌 때까지 하나씩 대기열에서 꺼냅니다. 이는 모든 유효한 요소가 순회되었음을 의미합니다. .

위 내용은 혼란스러운 지하철을 통과하기 위해 Python에서 너비 우선 검색을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!