ধরি আমাদের কাছে n শীর্ষবিশিষ্ট একটি অনির্দেশিত ট্রি (undirected tree) আছে। শীর্ষগুলো 1 থেকে n পর্যন্ত নম্বর করা আছে। এখন একটি মেঢো শীর্ষ 1 থেকে লাফানোর শুরু করে। মেঢোটি তার বর্তমান শীর্ষ থেকে অন্য কোনো অনভিজিট করা শীর্ষে লাফাতে পারে যদি সেগুলো смеж (adjacent) হয়, এটি এক সেকেন্ড সময় নেয়। মেঢোটি কোনো ভিজিট করা শীর্ষে ফিরে যেতে পারে না। যদি মেঢোটি একাধিক শীর্ষে লাফাতে পারে, তবে এটি সমান সম্ভাবনার সাথে যেকোনো একটি বেছে নেয়।
অন্যদিকে, যখন মেঢোটি কোনো অনভিজিট করা শীর্ষে লাফাতে পারে না, তবে এটি চিরকাল একই শীর্ষে লাফিয়ে থাকে।
ট্রিটি এজ (edge) এর একটি অ্যারে হিসেবে দেওয়া আছে। আমাদের t সেকেন্ড পর মেঢোটি target শীর্ষে আছে কিনা তার সম্ভাবনা বের করতে হবে।
তাহলে, ইনপুট যদি হয়: n = 7, t = 2, target = 4 এবং ট্রিটি হয় –
তাহলে আউটপুট হবে 0.1666, কারণ গ্রাফ থেকে দেখা যায়। মেঢো শীর্ষ 1 থেকে শুরু করে, প্রথম সেকেন্ডে 0.3333 সম্ভাবনার সাথে শীর্ষ 2-এ লাফায় এবং দ্বিতীয় সেকেন্ডে 0.5 সম্ভাবনার সাথে শীর্ষ 4-এ লাফায়। তাই 2 সেকেন্ড পর মেঢোর শীর্ষ 4-এ থাকার সম্ভাবনা = 0.3333 * 0.5 = 0.16665।
সমাধানের ধাপসমূহ
ret := 1
একটি visited সেট সংজ্ঞায়িত করুন
একটি dfs() ফাংশন সংজ্ঞায়িত করুন, যা নেবে node, start, এজের লিস্ট g, time, t, একটি স্ট্যাক st
যদি node visited সেটের সদস্য হয়, তবে –
false ফেরত দিন
node কে visited সেটে যোগ করুন
যদি node 1-এর সমান হয়, তবে –
tt := time, ok := true
true ফেরত দিন
i := 0 থেকে g[node] এর আকার পর্যন্ত লুপ চালান –
g[node, i] কে st-এ যোগ করুন
যদি dfs(g[node, i], start, g, time + 1, t, st) true ফেরত দেয়, তবে –
true ফেরত দিন
st থেকে উপাদান মুছে দিন
false ফেরত দিন
মূল পদ্ধতিতে নিম্নলিখিত কাজ করুন –
ret := 1
ok := false
n+1 আকারের একটি অ্যারে অফ লিস্ট graph সংজ্ঞায়িত করুন
n+1 আকারের একটি অ্যারে অফ লিস্ট graph2 সংজ্ঞায়িত করুন
i := 0 থেকে edges এর আকার পর্যন্ত লুপ চালান –
edges[i, 1] কে graph[edges[i, 0]]-এর শেষে যোগ করুন
edges[i, 0] কে graph[edges[i, 1]]-এর শেষে যোগ করুন
একটি স্ট্যাক st সংজ্ঞায়িত করুন
dfs(target, target, graph, 0, t, st) কল করুন
যখন st খালি না হয়, লুপ চালান –
node := st-এর উপরের উপাদান
sz := graph[node] এর আকার
যদি node 1-এর সমান না হয়, তবে –
(sz 1 কমানো)
ret := ret * (1.0 / sz)
st থেকে উপাদান মুছে দিন
যদি tt > t হয়, তবে –
0 ফেরত দিন
যদি tt == t হয়, তবে –
ret ফেরত দিন
যদি tt < t এবং target == 1 এবং graph[target] এর আকার >= 1 হয়, তবে –
0 ফেরত দিন
ফেরত দিন (যদি tt < t এবং graph[target] এর আকার > 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
