C++ में ज़ूमा गेम

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

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

मेज पर सभी गेंदों को हटाने के लिए हमें कम से कम गेंदें डालनी होंगी। अगर हम सभी गेंदों को नहीं हटा सकते हैं, तो -1 लौटा दें।

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

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

• एक फ़ंक्शन को परिभाषित करें findMinStep(), इसमें s, हाथ लगेगा,
• s :=s "#" को जोड़ना
• 26 आकार की एक सरणी v परिभाषित करें
• इनिशियलाइज़ i :=0 के लिए, जब i <हाथ का आकार, अपडेट करें (i से 1 बढ़ाएँ), −
  करें
  • v[hand[i] - 'A'] को 1 से बढ़ाएं
• ret :=फ़ंक्शन को कॉल करें हल करें(s, v)
• रिटर्न रिट>=यदि आईएनएफ शून्य नहीं है तो -1 से चेक करें अन्यथा रिट के साथ
• एक फ़ंक्शन को हल करें परिभाषित करें (), इसमें s, एक सरणी v,
लगेगा
• यदि s "#" के समान है, तो −
  • वापसी 0
• रिट:=आईएनएफ
• इनिशियलाइज़ करने के लिए i :=0, j :=0, जब j करें
• यदि s[i], s[j] के समान है, तो −
  • निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
• जरूरत:=3 - (जे-आई)
• x :=s[i]
• यदि आवश्यकता हो <=v[x - 'A'], तो −
  • v[x - 'A'] =v[x - 'A'] - जरूरत
  • ret :=न्यूनतम रिट और आवश्यकता + हल (0 से ith इंडेक्स में s का सबस्ट्रिंग) s को j से s के आकार के सबस्ट्रिंग में संयोजित करें – j, v
  • v[x - 'A'] =v[x - 'A'] + ज़रूरत
• i :=j

#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