C++ में जूमा गेम समस्या

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

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

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

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

समाधान दृष्टिकोण (DFS + बैकट्रैकिंग)

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

प्रोसेस फंक्शन:

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

C++ कार्यान्वयन

#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, 0);
        for (char c : hand) v[c - '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;
        
        // प्रयास 1: डालने से पहले कोई ऑटो-रिमूवल नहीं
        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;
                string next = s.substr(0, i) + s.substr(j);
                ret = min(ret, need + solve(next, v));
                v[x - 'A'] += need;
            }
            i = j;
        }
        
        // स्वचालित हटाने को प्रोसेस करें
        process(s);
        if (s == "#") return 0;
        
        // प्रयास 2: ऑटो-रिमूवल के बाद
        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;
                string next = s.substr(0, i) + s.substr(j);
                ret = min(ret, need + solve(next, 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;
            }
        }
    }
};

int main() {
    Solution ob;
    cout << ob.findMinStep("WRRBBW", "RBW");
    return 0;
}

इनपुट

"WRRBBW", "RBW"

आउटपुट

3