เกม Zuma ใน C ++

ให้เราพิจารณาเกี่ยวกับเกม Zuma สมมติว่าเรามีลูกบอลอยู่หนึ่งแถวบนโต๊ะ ลูกบอลเหล่านี้มีสีเป็นสีแดง(R), สีเหลือง(Y), สีน้ำเงิน(B), สีเขียว(G) และสีขาว(W) เรามีลูกบอลหลายลูกติดตัวไปด้วย

แต่ละครั้ง เราอาจเลือกลูกบอลจากฝั่งเรา และสอดเข้าไปในแถว จากนั้น ถ้ามีกลุ่มลูก 3 ลูกขึ้นไปที่มีสีเดียวกันสัมผัสกัน ให้นำออก ทำเช่นนี้ต่อไปจนกว่าจะไม่สามารถเอาลูกบอลออกได้อีกต่อไป

เราต้องหาลูกบอลขั้นต่ำที่เราต้องใส่เพื่อเอาลูกบอลทั้งหมดบนโต๊ะออก หากเราไม่สามารถเอาลูกบอลทั้งหมดออก ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นเหมือน "WRRBBW" และเรามี "RBW" คำตอบจะเป็น 3 เราสามารถเพิ่ม R หลัง RR (WRR[R]BBW) หลังจากลบ ลำดับจะเป็น (WBBW) จากนั้นเพิ่ม B ดังนั้น (WBB[B]W) หลังจากลบแล้ว จะเป็น (WW) จากนั้นเพิ่ม W ดังนั้นลำดับจะเป็น (WW[W]) การดำเนินการนี้จะลบลูกบอลทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน findMinStep() ซึ่งจะใช้ s มือ
s :=s concatenate "#"
กำหนดอาร์เรย์ v ขนาด 26
สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของมือ อัปเดต (เพิ่ม 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 อัปเดต (เพิ่ม j ทีละ 1) ทำ −
- ถ้า s[i] เหมือนกับ s[j] แล้ว −
  - ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
- need :=3 - (j - i)
- x :=s[i]
- ถ้าต้องการ <=v[x - 'A'] แล้ว −
  - v[x - 'A'] =v[x - 'A'] - ต้องการ
  - ret :=ขั้นต่ำของ ret และ need + การแก้ปัญหา (สตริงย่อยของ s จาก 0 ถึงดัชนี ith) เชื่อมสตริงย่อยของ s จาก j เป็นขนาดของ s – j, v
  - v[x - 'A'] =v[x - 'A'] + ต้องการ
- ผม :=เจ
เรียกกระบวนการทำงาน
ถ้า s เหมือนกับ "#" แล้ว −
- คืน 0
สำหรับการเริ่มต้น i :=0, j :=0 เมื่อ j <ขนาดของ s อัปเดต (เพิ่ม j ทีละ 1) ทำ −
- ถ้า s[i] เหมือนกับ s[j] แล้ว −
  - ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
- need :=3 - (j - i)
- x :=s[i]
- ถ้าต้องการ <=v[x - 'A'] แล้ว −
  - v[x - 'A'] =v[x - 'A'] - ต้องการ
  - ret :=ขั้นต่ำของ ret และ need + การแก้ปัญหา (สตริงย่อยของ s จาก 0 ถึงดัชนี ith) เชื่อมสตริงย่อยของ s จาก j เป็นขนาดของ s – j, v
  - v[x - 'A'] =v[x - 'A'] + ต้องการ
- ผม :=เจ
คืนสินค้า
กำหนดฟังก์ชัน process() ซึ่งจะใช้เวลา s
สำหรับการเริ่มต้น i :=0, j :=0 เมื่อ j <ขนาดของ s อัปเดต (เพิ่ม j ทีละ 1) ทำ −
- ถ้า s[i] เหมือนกับ s[j] แล้ว −
  - ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
- ถ้า (j - i)>=3 แล้ว −
  - ลบ i, j - i จาก s
  - j :=i - 1
- มิฉะนั้น
  - ผม :=เจ
เรียก findMinStep() ด้วยสองสตริงเพื่อรับคำตอบ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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"

เกม Zuma ใน C ++

ตัวอย่าง

อินพุต

ผลลัพธ์