เกมซูมา (Zuma Game) ใน C++

ภาพรวมปัญหา

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

ตัวอย่าง

Board: "WRRBBW", Hand: "RBW" → Output: 3

แทรก R หลัง RR → WRR[R]BBW → หาย RRR → WBBW

แทรก B → WBB[B]W → หาย BBB → WW

แทรก W → WW[W] → หาย WWW → ว่าง

แนวทางแก้ปัญหา (DFS + Backtracking)

State: สตริงบนโต๊ะ (ต่อ '#' ท้าย) + จำนวนลูกบอลแต่ละสีในมือ
DFS: ลองแทรกลูกบอลที่มีในมือเข้าแต่ละกลุ่มลูกบอลติดกันสีเดียวกัน
ต้องการ 3 - (ขนาดกลุ่ม) ลูกเพื่อทำให้หาย
หลังแทรก เรียก process() กำจัดกลุ่ม ≥3 ติดกันซ้ำจนหมด
Pruning: ถ้าจำนวนลูกในมือไม่พอ ข้าม
Memoization ไม่ได้ใช้ (state space ใหญ่) แต่ DFS + pruning พอสำหรับ constraints

ตัวอย่างโปรแกรม

#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;
        
        // ลองแทรกก่อน process
        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), v));
                v[x - 'A'] += need;
            }
            i = j;
        }
        
        // Process: กำจัดกลุ่ม ≥3
        process(s);
        if(s == "#") return 0;
        
        // ลองแทรกหลัง process
        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), 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;
        }
    }
};

int main() {
    Solution ob;
    cout << (ob.findMinStep("WRRBBW", "RBW"));
}

Input

"WRRBBW", "RBW"