C++ এ বাসের রুট

ধরুন আমাদের বাস রুটের একটি তালিকা আছে। প্রতিটি রুটে[i] একটি বাস রুট রয়েছে যা i-th বাস চিরতরে পুনরাবৃত্তি করে। সুতরাং, যদি রুট[0] =[1, 5, 7], তাহলে এর মানে হল প্রথম বাস (0-তম সূচীকৃত) ক্রম 1, 5, 7, 1, 5, 7, 1, ... চিরতরে ভ্রমণ করে .

এখন ধরুন আমরা বাস স্টপে এস থেকে শুরু করি, প্রাথমিকভাবে বাসে নয়, এবং আমরা বাস স্টপে T-এ যেতে চাই। আমাদের গন্তব্যে পৌঁছানোর জন্য আমাদের কমপক্ষে সংখ্যক বাস নিতে হবে? যদি এটি সম্ভব না হয় তবে -1 ফেরত দিন।

সুতরাং যদি ইনপুট হয় [[1,2,8],[3,6,8]], এবং S =1, T =6, তাহলে আউটপুট হবে 2। সুতরাং, প্রথম বাসটি বাস স্টপে 7 এ নিন, তারপর দ্বিতীয় বাসে উঠুন ৬ নম্বর বাসস্টপে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র m সংজ্ঞায়িত করুন
• আরম্ভ করার জন্য i :=0, যখন i
• আরম্ভ করার জন্য j :=0, যখন j করুন
• m[r[i, j]] এর শেষে i ঢোকান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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