आइए जूमा गेम (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
- यदि s[i], s[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
- यदि s[i], s[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
- यदि s[i], s[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