ধরুন আমাদের একটি অনির্দেশিত গাছ আছে যা n শীর্ষবিন্দু নিয়ে গঠিত। শীর্ষবিন্দুগুলি 1 থেকে n পর্যন্ত সংখ্যাযুক্ত। এখন একটি ব্যাঙ শীর্ষবিন্দু 1 থেকে লাফ দিতে শুরু করে। ব্যাঙটি তার বর্তমান শীর্ষবিন্দু থেকে অন্য অ-দর্শিত শীর্ষবিন্দুতে লাফ দিতে পারে যদি তারা সংলগ্ন থাকে, এক সেকেন্ডে। ব্যাঙ একটি পরিদর্শন শীর্ষবিন্দু ফিরে লাফ দিতে পারে না. যদি ব্যাঙটি বেশ কয়েকটি শীর্ষে লাফ দিতে পারে তবে এটি এলোমেলোভাবে তাদের একটিতে লাফ দেয়
যেখানে সম্ভাবনা একই, অন্যথায়, ব্যাঙ যখন কোনো অ-দর্শিত শীর্ষবিন্দুতে লাফ দিতে পারে না তখন এটি একই শীর্ষে চিরতরে লাফ দেয়।
গাছটি প্রান্তের অ্যারে হিসাবে দেওয়া হয়। আমাদের সম্ভাব্যতা খুঁজে বের করতে হবে যে t সেকেন্ড পরে ব্যাঙটি শীর্ষবিন্দু লক্ষ্যে রয়েছে।
সুতরাং, যদি ইনপুট n এর মত হয় 7, t হয় 2, লক্ষ্য 4 এবং গাছটি হয় −
তারপর আউটপুট হবে 0.1666, গ্রাফ থেকে। ব্যাঙটি শীর্ষবিন্দু 1 থেকে শুরু হয়, দ্বিতীয় 1 এর পরে শীর্ষ 2 তে 0.3333 সম্ভাবনা নিয়ে লাফ দেয় এবং তারপর 0.5 সম্ভাবনা নিয়ে দ্বিতীয় 2 এর পরে শীর্ষবিন্দু 4 এ ঝাঁপ দেয়। এইভাবে 2 সেকেন্ডের পরে 4 শীর্ষবিন্দুতে ব্যাঙের সম্ভাবনা 0.3333 * =0.5 1.6665।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=1
-
পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন
-
একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, স্টার্ট, প্রান্তের তালিকা g, সময়, টি, এক স্ট্যাক st,
-
যদি নোড ভিজিট করা হয়, তাহলে −
-
ফেরত মিথ্যা
-
-
ভিজিটেড
-এ নোড সন্নিবেশ করান -
যদি নোড 1 এর মত হয়, তাহলে −
-
tt :=সময়, ঠিক আছে :=সত্য
-
প্রত্যাবর্তন সত্য
-
-
আরম্ভ করার জন্য i :=0, যখন i
-
st
এ g[নোড, i] সন্নিবেশ করান -
যদি dfs(g[নোড, i], start, g, time + 1, t, st) সত্য হয়, তাহলে −
-
প্রত্যাবর্তন সত্য
-
-
st
থেকে উপাদান মুছুন
-
-
ফেরত মিথ্যা
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
ret :=1
-
ঠিক আছে :=মিথ্যা
-
n + 1
আকারের তালিকার গ্রাফের একটি অ্যারে সংজ্ঞায়িত করুন -
n + 1
আকারের গ্রাফ2 তালিকার একটি অ্যারে সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i <প্রান্তের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
গ্রাফের শেষে প্রান্ত [i, 1] সন্নিবেশ করান
-
গ্রাফের শেষে প্রান্ত [i, 0] সন্নিবেশ করান
-
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
dfs(লক্ষ্য, লক্ষ্য, গ্রাফ, 0, t, st)
-
যখন (st খালি নয়), −
করুন-
নোড :=st এর শীর্ষ উপাদান
-
sz :=গ্রাফের আকার [নোড]
-
যদি নোড 1 এর সমান না হয়, তাহলে −
-
(1 দ্বারা sz কমান)
-
-
ret :=ret * (1.0 / sz)
-
st
থেকে উপাদান মুছুন
-
-
যদি tt> t, তাহলে −
-
ফেরত 0
-
-
যদি tt টি হয়, তাহলে −
-
রিটার্ন রিটার্ন
-
-
যদি tt
=1 হয়, তাহলে − -
ফেরত 0
-
-
রিটার্ন (যদি tt
1, তারপর 0, অন্যথায় ret)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double ret = 1;
bool ok;
set<int> visited;
int tt;
bool dfs(int node, int start, vector<int> g[], int time, int t,
stack<int>& st){
if (visited.count(node))
return false;
visited.insert(node);
if (node == 1) {
tt = time;
ok = true;
return true;
}
for (int i = 0; i < g[node].size(); i++) {
st.push(g[node][i]);
if (dfs(g[node][i], start, g, time + 1, t, st))
return true;
;
st.pop();
}
return false;
}
double frogPosition(int n, vector<vector<int> >& edges, int t,
int target){
ret = 1;
ok = false;
vector<int> graph[n + 1];
vector<int> graph2[n + 1];
for (int i = 0; i < edges.size(); i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
stack<int> st;
dfs(target, target, graph, 0, t, st);
while (!st.empty()) {
int node = st.top();
double sz = (double)graph[node].size();
if (node != 1)
sz--;
ret *= (1.0 / sz);
st.pop();
}
if (tt > t)
return 0;
if (tt == t)
return ret;
if (tt < t && target == 1 && graph[target].size() >= 1)
return 0;
return tt < t && graph[target].size() > 1 ? 0 : ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
cout << (ob.frogPosition(7,v,2,4));
} ইনপুট
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4 আউটপুট
0.166667
