জুমা গেম বিবেচনা করুন। টেবিলে রঙিন বলের একটি সারি আছে: লাল(R), হলুদ(Y), নীল(B), সবুজ(G), সাদা(W)। আমাদের হাতেও কিছু বল আছে।
প্রতিবার আমরা হাত থেকে একটি বল বেছে নিয়ে সারিতে ঢুকিয়ে দিতে পারি। তারপর যদি ৩ বা অধিক একই রঙের বল স্পর্শ করে থাকে, তবে সেগুলো সরিয়ে ফেলা হয়। এটি চলতে থাকবে যতক্ষণ না আর কোনো বল সরানো সম্ভব নয়।
টেবিলের সব বল সরিয়ে ফেলার জন্য ন্যূনতম কতটি বল ঢুকিয়ে দিতে হবে তা বের করতে হবে। অসম্ভব হলে -1 রিটার্ন করুন।
ইনপুট "WRRBBW" এবং হাতে "RBW" হলে, উত্তর ৩। R বসিয়ে RRR বানালে WBBW, তারপর B বসিয়ে WBBBW -> WW, তারপর W বসিয়ে WWW -> সব মুছে যাবে।
সমাধানের ধাপসমূহ
- findMinStep(s, hand) ফাংশন:
- s += "#", হাতের বলের কাউন্ট v[26] এ রাখুন
- ret := solve(s, v), ret >= INF হলে -1 রিটার্ন
- solve(s, v) ফাংশন:
- যদি s == "#", ০ রিটার্ন
- ret := INF
- সन्नিহিত একই রঙের গ্রুপ খুঁজে বের করুন, need := 3 - গ্রুপ সাইজ
- যদি need <= v[x], v[x] কমিয়ে রিকার্সিভ কল করুন, ব্যাকট্র্যাক করুন
- process(s) কল করে স্বয়ংক্রিয় রিমUভাল করুন
- আবার গ্রুপ খুঁজে রিকার্সিভ কল করুন
- ret রিটার্ন
- process(s): ৩ বা অধিক সন্নিহিত একই রঙের বল মুছে ফেলুন
উদাহরণ
#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
