Zuma Game: เกมซูมาหาลูกบอลน้อยที่สุดใน C++

ปัญหา

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

ตัวอย่าง: board="WRRBBW", hand="RBW" → 3 ลูก

แนวคิด: DFS + Backtracking + Pruning

State

• board: สตริงลูกบอลปัจจุบัน (เพิ่ม # ท้ายเป็น Sentinel)
• hand[26]: จำนวนลูกบอลแต่ละสีบนมือ

Recursive Function

solve(board, hand) = ลูกบอลน้อยที่สุดที่ต้องใช้จาก state นี้

Transition

1. Process board: กำจัดกลุ่ม 3+ ติดกันซ้ำจนไม่มี (Function process())
2. Base case: board == "#" → 0
3. ลองแทรก: สำหรับแต่ละกลุ่มสีเดียวกันติดกันบน board (ความยาว len):
   • ต้องการ need = 3 - len ลูกเพื่อทำให้ครบ 3
   • ถ้ามือมีพอ → ลองแทรก (ลด hand, เรียก solve ใหม่, คืน hand)
4. คืนค่าต่ำสุด

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

class Solution {
    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 solve(string s, vector<int>& hand) {
        if (s == "#") return 0;
        process(s);
        if (s == "#") return 0;
        
        int ret = INF;
        for (int i = 0, j = 0; j < s.size(); j++) {
            if (s[i] == s[j]) continue;
            int len = j - i;
            int need = 3 - len;
            char color = s[i];
            if (need <= hand[color - 'A']) {
                hand[color - 'A'] -= need;
                string next = s.substr(0, i) + s.substr(j);
                ret = min(ret, need + solve(next, hand));
                hand[color - 'A'] += need;
            }
            i = j;
        }
        return ret;
    }
    
public:
    int findMinStep(string board, string hand) {
        board += "#";
        vector<int> handCount(26, 0);
        for (char c : hand) handCount[c - 'A']++;
        int ans = solve(board, handCount);
        return ans >= INF ? -1 : ans;
    }
};

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

การทำงานตัวอย่าง

Board: WRRBBW, Hand: RBW
1. แทรก R หลัง RR: WRR[R]BBW → WBBW (RRR หาย)
2. แทรก B ระหว่าง BB: WB[B]BW → WW (BBB หาย)
3. แทรก W: WW[W] → (WWW หาย) → ว่าง
Total: 3 balls

ความซับซ้อน

• Time: Exponential (แต่ Pruning ทำให้เร็วในทางปฏิบัติ)
• Space: O(board length × recursion depth)

Input / Output

Input:  "WRRBBW", "RBW"
Output: 3