C++でのZumaゲーム

ズマゲームについて考えてみましょう。テーブルにボールの列があるとすると、これらのボールは赤（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 <手のサイズの場合、更新（iを1増やします）、実行-
  • v[hand[i]-'A']を1増やします
• ret：=関数solve（s、v）を呼び出す
• return ret> =INFがゼロ以外の場合は、-1でチェックし、そうでない場合はretでチェックします
• 関数solve（）を定義します。これには、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とneedの最小値+solve（0からi番目のインデックスまでのsの部分文字列）は、jからsのサイズまでの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