เส้นทางรถบัส (Bus Routes) ใน C++

ภาพรวมปัญหา

สมมติว่าเรามีรายการเส้นทางรถบัส แต่ละ routes[i] เป็นเส้นทางที่รถบัสคันที่ i วิ่งซ้ำไปซ้ำมา ตัวอย่าง: routes[0] = [1, 5, 7] หมายถึงรถบัสคันแรกวิ่งตามลำดับ 1, 5, 7, 1, 5, 7, ... ตลอดเวลา

เราเริ่มที่ป้ายรถบัส S (ยังไม่ได้ขึ้นรถ) และต้องการไปป้าย T หาจำนวนรถบัสน้อยที่สุดที่ต้องขึ้นเพื่อไปถึงปลายทาง หากไม่สามารถไปได้ ให้คืนค่า -1

ตัวอย่าง

Input: [[1,2,8], [3,6,8]], S = 1, T = 6 → Output: 2

ขึ้นรถคันแรกไปป้าย 8 แล้วขึ้นรถคันที่สองไปป้าย 6

แนวทางแก้ปัญหา (BFS)

สร้าง map: ป้ายรถบัส → รายการรถบัสที่หยุดที่ป้ายนั้น
BFS จากป้ายเริ่มต้น S โดยแต่ละระดับ = จำนวนรถบัสที่ขึ้น
จากป้ายปัจจุบัน ดูรถบัสที่หยุดที่นั่น → จากรถบัสนั้น ดูป้ายทั้งหมดที่รถคันนั้นหยุด
ถ้าเจอป้าย T คืนค่าระดับปัจจุบัน
ใช้ set เก็บรถบัสที่ใช้แล้ว เพื่อไม่ให้ขึ้นซ้ำ

ตัวอย่างโปรแกรม

#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;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,2,8}, {3,6,8}};
    cout << (ob.numBusesToDestination(v, 1, 6));
}

Input

{{1,2,8}, {3,6,8}} 1 6