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])। এটি সমস্ত বল মুছে ফেলবে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন findMinStep() সংজ্ঞায়িত করুন, এটি s, hand,
লাগবে
• s :=s concatenate "#"
• 26 আকারের একটি অ্যারে সংজ্ঞায়িত করুন
• আরম্ভ করার জন্য i :=0, যখন i <হাতের আকার, আপডেট (i 1 দ্বারা বাড়ান), −
  করুন
  • v[hand[i] - 'A'] 1 দ্বারা বাড়ান
• ret :=ফাংশন solve(s, v) কল করুন
• রিটার্ন রিটার্ন>=INF যদি শূন্য না হয় তাহলে - 1 দিয়ে চেক করুন অন্যথায় ret সহ
• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এতে s, একটি অ্যারে v,
লাগবে
• যদি s "#" এর মত হয়, তাহলে −
  • রিটার্ন 0
• ret :=INF
• আরম্ভ করার জন্য i :=0, j :=0, যখন j করুন
• যদি s[i] s[j] এর মত হয়, তাহলে −
  • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
• প্রয়োজন :=3 - (j - i)
• x :=s[i]
• যদি প্রয়োজন হয় <=v[x - 'A'], তারপর −
  • v[x - 'A'] =v[x - 'A'] - প্রয়োজন
  • ret :=ন্যূনতম 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