버스 노선 목록이 있다고 가정합니다. 각 노선[i]에는 i번째 버스가 영원히 반복되는 버스 노선이 있습니다. 따라서 route[0] =[1, 5, 7]이면 첫 번째 버스(0번째 인덱싱됨)가 1, 5, 7, 1, 5, 7, 1, ... 영원히 시퀀스로 이동함을 의미합니다. .
이제 처음에는 버스가 아닌 S 버스 정류장에서 출발하고 T 버스 정류장으로 가고 싶다고 가정합니다. 목적지에 도달하기 위해 타야 하는 버스의 최소 수를 찾아야 합니까? 이것이 불가능하면 -1을 반환하십시오.
따라서 입력이 [[1,2,8],[3,6,8]]이고 S =1, T =6이면 출력은 2가 됩니다. 따라서 첫 번째 버스를 타고 7번 버스 정류장으로 이동합니다. 그런 다음 두 번째 버스를 타고 6번 버스 정류장으로 갑니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 하나의 지도 정의
- 초기화 i의 경우:=0, i
- j 초기화의 경우:=0, j
- m[r[i, j]] 끝에 i 삽입
- j 초기화의 경우:=0, j
- 0을 반환
- 을 수행합니다.
- sz :=q의 크기
- sz가 0이 아닌 동안 −
- node :=q의 첫 번째 요소, q에서 요소 삭제
- 초기화 i의 경우:=0, i
- 경로:=m[노드, i]
- 경로가 방문 중인 경우 -
- 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- 방문 경로 삽입
- j 초기화의 경우:=0, j
- 정지 :=r[경로, j]
- stop이 T와 같으면 -
- 반환 레벨
- q에 정류장 삽입
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& r, int S, int T) {
unordered_map <int, vector <int> > m;
for(int i = 0; i < r.size(); i++){
for(int j = 0; j < r[i].size(); j++){
m[r[i][j]].push_back(i);
}
}
queue <int> q;
q.push(S);
if(S == T) return 0;
unordered_set <int> visited;
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
int node = q.front();
q.pop();
for(int i = 0; i < m[node].size(); i++){
int route = m[node][i];
if(visited.count(route)) continue;
visited.insert(route);
for(int j = 0; j < r[route].size(); j++){
int stop = r[route][j];
if(stop == T) return lvl;
q.push(stop);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,8}, {3,6,8}};
cout << (ob.numBusesToDestination(v, 1, 6));
} 입력
{{1,2,8}, {3,6,8}}
1
6 출력
2