เส้นทางรถเมล์ใน C++

สมมติว่าเรามีรายการเส้นทางรถเมล์ ในแต่ละเส้นทาง[i] จะมีเส้นทางรถเมล์ที่ i-th บัสวนซ้ำตลอดไป ดังนั้น หากเส้นทาง[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 แล้วต่อรถสายที่ 2 มาที่ป้าย 6.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดหนึ่งแผนที่ m
สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของ r อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ r[i] อัปเดต (เพิ่ม j ทีละ 1) ทำ −
  - ใส่ i ต่อท้าย m[r[i, j]]
กำหนดหนึ่งคิว q ใส่ S ลงใน q
ถ้า S เหมือนกับ T แล้ว −
- คืน 0
กำหนดชุดหนึ่งเรียกว่าเยี่ยมชมแล้ว
สำหรับการเริ่มต้น lvl :=1 เมื่อไม่มี q ว่างเปล่า ให้อัปเดต (เพิ่มระดับทีละ 1) ทำ −
- sz :=ขนาดของ q
- ในขณะที่ sz ไม่ใช่ศูนย์ ให้ทำ −
  - โหนด :=องค์ประกอบแรกของ q ลบองค์ประกอบออกจาก q
  - สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ m[node] อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
    - เส้นทาง :=m[node, i]
    - หากมีการเยี่ยมชมเส้นทาง −
      - ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
    - แทรกเส้นทางเข้าเยี่ยมชม
    - สำหรับการเริ่มต้น j :=0 เมื่อ j <ขนาดของ r[route] อัปเดต (เพิ่ม j โดย 1) ทำ −
      - หยุด :=r[route, j]
      - ถ้าการหยุดเหมือนกับ T แล้ว −
        
        คืนเลเวล
    - แทรกจุดหยุดลงใน q
  - ลด sz ลง 1
คืน -1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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

เส้นทางรถเมล์ใน C++

ตัวอย่าง

อินพุต

ผลลัพธ์