জুমা গেম (Zuma Game) নিয়ে চিন্তা করি। ধরুন টেবিলে একটি সারিয়ে বল রয়েছে, যেগুলো লাল(R), হলদে(Y), নীল(B), সবুজ(G), এবং সাদা(W) রঙে রঙ করা। আমাদের হাতে ও কিছু বল রয়েছে।
এখন, প্রতিবার, আমরা আমাদের পাশ থেকে একটি বল বেছে নিতে পারি, এবং সেটি সারির মধ্যে ইনসার্ট করতে পারি। তারপর, যদি ৩ বা তার অধিক একই রঙের বল স্পর্শ করে থাকে, তবে সেগুলো রিমুভ হয়ে যাবে। এটি চলতে থাকবে যতক্ষণ না আর কোনো বল রিমুভ করা সম্ভব না থাকে।
আমাদের টেবিলের সব বল রিমুভ করার জন্য আমাদের হাতে থেকে ন্যূনতম কতটি বল ইনসার্ট করতে হবে তা বের করতে হবে। যদি সব বল রিমুভ করা সম্ভব না হয়, তবে -1 ফেরত দিন।
সুতরাং যদি ইনপুট হয় "WRRBBW", এবং আমাদের হাতে "RBW" থাকে, তবে উত্তর হবে ৩। আমরা 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 1 বাড়ান), করুন:
- 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 1 বাড়ান), করুন:
- যদি 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 1 বাড়ান), করুন:
- যদি 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 1 বাড়ান), করুন:
- যদি 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
