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]], और एस =1, टी =6 जैसा है, तो आउटपुट 2 होगा। तो, बस स्टॉप 7 के लिए पहली बस लें, फिर बस स्टॉप 6 के लिए दूसरी बस लें।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक मानचित्र को परिभाषित करें मी
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• इनिशियलाइज़ j :=0 के लिए, जब j
• m के अंत में i डालें[r[i, j]]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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