মনে করুন, আমাদের কাছে বাস রুটের একটি তালিকা আছে। প্রতিটি routes[i]-তে i-তম বাসের রুট থাকে যা সেটি চিরকাল আবার্তন করে। যেমন, routes[0] = [1, 5, 7] মানে প্রথম বাস (০-ইনডেক্সড) ১, ৫, ৭, ১, ৫, ৭, ১, ... এই ক্রমে চলে।
এখন, আমরা বাস স্টপ S-তে শুরু করি (প্রাথমিকভাবে বাসে নই), এবং আমরা বাস স্টপ T-তে যেতে চাই। লক্ষ্য পর্যন্ত পৌঁছানোর জন্য ন্যূনতম কতটি বাস চড়তে হবে তা বের করতে হবে। যদি সম্ভব না হয়, তবে -1 রিটার্ন করুন।
যেমন, ইনপুট [[1,2,8],[3,6,8]], S = 1, T = 6 হলে, আউটপুট হবে ২। প্রথম বাসে চড়ে ৮ নম্বর স্টপে নেমে, তারপর দ্বিতীয় বাসে চড়ে ৬ নম্বর স্টপে পৌঁছাতে হবে।
সমাধানের ধাপসমূহ
- একটি ম্যাপ m সংজ্ঞায়িত করুন
- প্রতিটি রুট i এবং তার প্রতিটি স্টপ j এর জন্য, m[r[i][j]]-এ i যোগ করুন
- একটি কিউ q সংজ্ঞায়িত করুন, S কে q-তে ঢুকান
- যদি S == T হয়, তবে ০ রিটার্ন করুন
- একটি visited সেট সংজ্ঞায়িত করুন
- lvl := 1 থেকে শুরু করে q খালি না হওয়া পর্যন্ত লুপ চালান
- sz := q.size()
- যখন sz != 0
- node := q.front(), q.pop()
- m[node] এর প্রতিটি রুটের জন্য
- যদি রুটটি visited-এ থাকে, তবেiếp tục করুন
- রুটটি visited-এ যোগ করুন
- রুটটির প্রতিটি স্টপের জন্য
- যদি স্টপটি == T হয়, তবে lvl রিটার্ন করুন
- স্টপটি q-তে ঢুকান
- sz কমান
- -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
আউটপুট
2
