मान लीजिए हमारे पास n शीर्षों वाला एक अविकल्पित वृक्ष है। शीर्ष 1 से n तक संख्यांकित हैं। अब एक मेंढक शीर्ष 1 से कूदना शुरू करता है। मेंढक अपने वर्तमान शीर्ष से दूसरे अनदेखे शीर्ष पर कूद सकता है यदि वे आसन्न हैं, एक सेकंड में। मेंढक किसी देखे गए शीर्ष पर वापस नहीं कूद सकता। यदि मेंढक कई शीर्षों पर कूद सकता है तो वह उनमें से किसी एक पर यादृच्छिक रूप से कूदता है जहां संभावना समान होती है, अन्यथा जब मेंढक किसी अनदेखे शीर्ष पर नहीं कूद सकता तो वह उसी शीर्ष पर हमेशा के लिए कूदता रहता है।
वृक्ष को किनारों की सरणी के रूप में दिया गया है। हमें वह संभावना ज्ञात करनी है कि t सेकंड के बाद मेंढक शीर्ष target पर है।
यदि इनपुट है: n = 7, t = 2, target = 4 और वृक्ष है -

तो आउटपुट 0.1666 होगा, क्योंकि ग्राफ से: मेंढक शीर्ष 1 से शुरू होता है, 0.3333 संभावना के साथ 1 सेकंड के बाद शीर्ष 2 पर कूदता है और फिर 0.5 संभावना के साथ 2 सेकंड के बाद शीर्ष 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 वापस करें
g[node] के सभी आसन्न शीर्षों के लिए पुनरावृत्ति करें
मुख्य विधि से: ret := 1, ok := false, ग्राफ बनाएं, dfs कॉल करें, स्टैक से संभावना की गणना करें
यदि tt > t तो 0 वापस करें, यदि tt == t तो ret वापस करें, अन्यथा शर्तों के अनुसार 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];
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;
}
};
int 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));
return 0;
}
इनपुट
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4
आउटपुट
0.166667