Trò chơi Zuma trong C ++

Hãy để chúng tôi xem xét về trò chơi Zuma. Giả sử chúng ta có một hàng quả bóng trên bàn, những quả bóng này có màu đỏ (R), vàng (Y), xanh lam (B), xanh lá cây (G) và trắng (W). Chúng tôi cũng có một số quả bóng với chúng tôi.

Bây giờ, mỗi lần, chúng ta có thể chọn một quả bóng từ phía mình và chèn nó vào hàng. Sau đó, nếu có một nhóm gồm 3 quả bóng cùng màu trở lên chạm vào nhau, hãy loại bỏ chúng. Tiếp tục làm như vậy cho đến khi không thể lấy được bóng nữa.

Chúng ta phải tìm những quả bóng tối thiểu mà chúng ta phải chèn để loại bỏ tất cả các quả bóng trên bàn. Nếu chúng ta không thể loại bỏ tất cả các quả bóng, hãy trả về -1.

Vì vậy, nếu đầu vào là “WRRBBW” và chúng ta có “RBW”, thì câu trả lời sẽ là 3. Chúng ta có thể thêm R vào sau RR, (WRR [R] BBW), sau khi loại bỏ, chuỗi sẽ là (WBBW), sau đó thêm B, do đó (WBB [B] W), sau khi loại bỏ nó sẽ là (WW), sau đó thêm W, do đó chuỗi sẽ là (WW [W]). Thao tác này sẽ loại bỏ tất cả các quả bóng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm findMinStep (), điều này sẽ thực hiện,
• s:=s nối "#"
• Xác định một mảng v có kích thước 26
• để khởi tạo i:=0, khi tôi
• tăng v [hand [i] - 'A'] lên 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

"WRRBBW", "RBW"

Đầu ra

3