Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में जूमा गेम (Zuma Game)


आइए जूमा गेम (Zuma Game) के बारे में विचार करें। मान लीजिए हमारे पास टेबल पर गेंदों की एक पंक्ति है, ये गेंदें लाल (R), पीली (Y), नीली (B), हरी (G), और सफेद (W) रंग की हैं। हमारे पास भी कई गेंदें हैं।

अब, प्रत्येक बार, हम अपनी तरफ से एक गेंद चुन सकते हैं, और इसे पंक्ति में डाल सकते हैं। फिर, यदि एक ही रंग की 3 या अधिक गेंदों का समूह छू रहा है, तो उन्हें हटा दें। इसे तब तक करते रहें जब तक कोई और गेंदें नहीं हटाई जा सकतीं।

हमें टेबल पर सभी गेंदों को हटाने के लिए डालने के लिए न्यूनतम गेंदें ज्ञात करनी हैं। यदि हम सभी गेंदों को नहीं हटा सकते, तो -1 वापस करें।

तो यदि इनपुट "WRRBBW" जैसा है, और हमारे पास "RBW" है, तो उत्तर 3 होगा। हम RR के बाद R जोड़ सकते हैं, (WRR[R]BBW), हटाने के बाद, अनुक्रम (WBBW) होगा, फिर B जोड़ें, तो (WBB[B]W), हटाने के बाद यह (WW) होगा, फिर W जोड़ें, तो अनुक्रम (WW[W]) होगा। यह सभी गेंदों को हटा देगा।

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

  • एक फंक्शन findMinStep() परिभाषित करें, यह s, hand लेगा,
  • s := s को "#" के साथ जोड़ें
  • आकार 26 का एक ऐरे v परिभाषित करें
  • i := 0 से प्रारंभ करें, जब i < hand का आकार, i बढ़ाते हुए, करें -
    • v[hand[i] - 'A'] को 1 से बढ़ाएं
  • ret := solve(s, v) फंक्शन कॉल करें
  • वापस करें ret >= INF है तो -1 के साथ जांचें अन्यथा ret के साथ
  • एक फंक्शन solve() परिभाषित करें, यह s, एक ऐरे v लेगा,
  • यदि s, "#" के समान है, तो -
    • 0 वापस करें
  • ret := INF
  • i := 0, j := 0 से प्रारंभ करें, जब j < s का आकार, j बढ़ाते हुए, करें -
    • यदि s[i], s[j] के समान है, तो -
      • अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
    • need := 3 - (j - i)
    • x := s[i]
    • यदि need <= v[x - 'A'], तो -
      • v[x - 'A'] = v[x - 'A'] - need
      • ret := ret का न्यूनतम और need + solve(s के 0 से i-थ इंडेक्स तक का सबस्ट्रिंग + s के j से s के आकार - j तक का सबस्ट्रिंग, v)
      • v[x - 'A'] = v[x - 'A'] + need
    • i := j
  • process(s) फंक्शन कॉल करें
  • यदि s, "#" के समान है, तो -
    • 0 वापस करें
  • i := 0, j := 0 से प्रारंभ करें, जब j < s का आकार, j बढ़ाते हुए, करें -
    • यदि s[i], s[j] के समान है, तो -
      • अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
    • need := 3 - (j - i)
    • x := s[i]
    • यदि need <= v[x - 'A'], तो -
      • v[x - 'A'] = v[x - 'A'] - need
      • ret := ret का न्यूनतम और need + solve(s के 0 से i-थ इंडेक्स तक का सबस्ट्रिंग + s के j से s के आकार - j तक का सबस्ट्रिंग, v)
      • v[x - 'A'] = v[x - 'A'] + need
    • i := j
  • ret वापस करें
  • एक फंक्शन process() परिभाषित करें, यह s लेगा,
  • i := 0, j := 0 से प्रारंभ करें, जब j < s का आकार, j बढ़ाते हुए, करें -
    • यदि s[i], s[j] के समान है, तो -
      • अगले भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
    • यदि (j - i) >= 3, तो -
      • s से i, j - i हटाएं
      • j := i - 1
    • अन्यथा
      • i := j
  • दो स्ट्रिंग्स के साथ findMinStep() कॉल करके उत्तर प्राप्त करें

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

उदाहरण

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; class Solution { public:    int findMinStep(string s, string hand) {       s += "#";       vector <int> v(26);       for(int i = 0; i < hand.size(); i++){          v[hand[i] - 'A']++;       }       int ret = solve(s, v);       return ret >= INF ? -1 : ret;    }    int solve(string s, vector <int>& v){       if(s == "#") return 0;       int ret = INF;       for(int i = 0, j = 0; j < s.size(); j++){          if(s[i] == s[j]) continue;          int need = 3 - (j - i);          char x = s[i];          if(need <= v[x - 'A']){             v[x - 'A'] -= need;             ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v)); v[x - 'A'] += need;          }          i = j;       }       process(s);       if(s == "#") return 0;       for(int i = 0, j = 0; j < s.size(); j++){          if(s[i] == s[j]) continue;          int need = 3 - (j - i);          char x = s[i];          if(need <= v[x - 'A']){             v[x - 'A'] -= need;             ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));             v[x - 'A'] += need;          }          i = j;       }       return ret;    }    void process(string& s){       for(int i = 0, j = 0; j < s.size(); j++){          if(s[i] == s[j]) continue;          if((j - i) >= 3){             s.erase(i, j - i);             j = i - 1;          } else i = j;       }    } }; main(){    Solution ob;    cout << (ob.findMinStep("WRRBBW", "RBW")); }

इनपुट

"WRRBBW", "RBW"

आउटपुट

3

  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ

  1. C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें अलग-अलग लेवल पर लीफ नोड्स हैं। एक और पॉइंटर दिया गया है, जो एक नोड को इंगित कर रहा है। हमें इंगित नोड से निकटतम लीफ नोड की दूरी ढूंढनी है। ट्री को नीचे जैसा मानें - यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड