혼란스러운 지하철을 통과하기 위해 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
        

         로그인 후 복사
        
       

Summary

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

Queen.append() while Queen: t=Queen.pop() if …… Queen.append()

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

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