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 :="#" 연결
• 크기가 26인 배열 v 정의
• 초기화 i의 경우:=0, i <손 크기일 때 업데이트(i 1 증가), −
  • v[hand[i] - 'A'] 1 증가
• ret :=solve(s, v) 함수 호출
• ret를 반환>=INF가 0이 아니면 검사 - 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의 최소값과 필요 + 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