C++ में T सेकंड के बाद मेंढक की स्थिति

मान लीजिए कि हमारे पास एक अप्रत्यक्ष वृक्ष है जिसमें n शीर्ष हैं। शीर्षों की संख्या 1 से n तक है। अब एक मेंढक शीर्ष 1 से कूदना शुरू करता है। मेंढक एक सेकंड में अपने वर्तमान शीर्ष से दूसरे गैर-विजिट किए गए शीर्ष पर कूद सकता है यदि वे आसन्न हैं। मेंढक वापस देखे गए शीर्ष पर नहीं जा सकता। यदि मेंढक कई शीर्षों पर कूद सकता है तो वह बेतरतीब ढंग से उनमें से किसी एक पर कूद सकता है

जहाँ प्रायिकता समान है, अन्यथा, जब मेंढक किसी भी गैर-विजिटेड शीर्ष पर कूद नहीं सकता है तो वह हमेशा के लिए उसी शीर्ष पर कूद जाता है।

पेड़ को किनारों की एक सरणी के रूप में दिया जाता है। हमें प्रायिकता ज्ञात करनी है कि t सेकंड के बाद मेंढक शीर्ष लक्ष्य पर है।

इसलिए, यदि इनपुट n जैसा है, तो 7 है, t 2 है, लक्ष्य 4 है और पेड़ जैसा है -

तो आउटपुट 0.1666 होगा, जैसा कि ग्राफ से है। मेंढक शीर्ष 1 से शुरू होता है, 0.3333 संभावना के साथ दूसरे 1 के बाद शीर्ष 2 पर कूदता है और फिर 0.5 संभावना के साथ दूसरे 2 के बाद शीर्ष 4 पर कूदता है। इस प्रकार 2 सेकंड के बाद मेंढक के लिए शीर्ष 4 पर संभावना 0.3333 * 0.5 =है 1.6665.

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

• रिट :=1

• देखे गए एक सेट को परिभाषित करें

• फ़ंक्शन dfs() को परिभाषित करें, यह नोड, प्रारंभ, किनारों की सूची g, समय, t, एक स्टैक st,

  लेगा

• यदि नोड विज़िट का सदस्य है, तो -

  • झूठी वापसी

• देखे गए में नोड डालें

• यदि नोड 1 के समान है, तो -

  • टीटी:=समय, ठीक:=सच

  • सही लौटें

• इनिशियलाइज़ करने के लिए:=0, जब i <आकार का g [नोड], अपडेट करें (i 1 से बढ़ाएँ), करें -

  • जी [नोड, आई] सेंट में डालें

  • यदि dfs(g[node, i], start, g, time + 1, t, st) सत्य है, तो -

    • सही लौटें

  • सेंट से तत्व हटाएं

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• रिट :=1

• ठीक :=असत्य

• आकार n + 1 के सूचियों की एक सरणी परिभाषित करें

• n + 1 के आकार की सूचियों की एक सरणी को परिभाषित करें ग्राफ़2

• इनिशियलाइज़ करने के लिए:=0, जब मैं <किनारों का आकार, अद्यतन (i से 1 बढ़ाएँ), करते हैं -

  • ग्राफ़ के अंत में किनारों[i, 1] डालें[किनारों[i, 0]]

  • ग्राफ़ के अंत में किनारों[i, 0] डालें[किनारों[i, 1]]

• एक स्टैक सेंट परिभाषित करें

• dfs (लक्ष्य, लक्ष्य, ग्राफ़, 0, t, st)

• जबकि (सेंट खाली नहीं है), करें -

  • नोड:=सेंट का शीर्ष तत्व

  • sz :=ग्राफ़ का आकार [नोड]

  • यदि नोड 1 के बराबर नहीं है, तो -

    • (sz को 1 से घटाएं)

  • रिट:=रिट * (1.0 / एसजेड)

  • सेंट से तत्व हटाएं

• अगर tt> t, तो -

  • वापसी 0

• यदि tt, t के समान है, तो -

  • वापसी रिट

• यदि tt =1 है, तो -

  • वापसी 0

• वापसी (यदि tt 1, तो 0, अन्यथा रिट करें)

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

उदाहरण

#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