Zuma Game trong C++

Cho dãy bi trên bàn (R,Y,B,G,W) và bi trên tay. Mỗi lượt chèn 1 bi vào dãy. Nếu có ≥3 bi cùng màu liên tiếp, xóa chúng. Lặp cho đến không xóa được. Tìm số bi chèn tối thiểu để xóa hết bàn. Không thể thì -1.

Ví dụ

board="WRRBBW", hand="RBW" → 3. Thêm R sau RR → WBBW, thêm B → WW, thêm W → xóa hết.

DFS + Backtracking

Đệ quy: tại mỗi trạng thái bàn, thử chèn bi từ tay vào các vị trí giữa các nhóm cùng màu. Nếu cần ≤ bi có sẵn, thử chèn, đệ quy, backtrack. Hàm process() xóa các nhóm ≥3 tự động.

Chương trình C++

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

class Solution {
    int solve(string s, vector<int>& hand) {
        if(s=="#") return 0;
        int ret = INF;
        // Thử chèn vào giữa các nhóm
        for(int i=0, j=0; j= 3) { s.erase(i, j-i); j = i-1; }
            else i = j;
        }
    }
public:
    int findMinStep(string board, string hand) {
        board += "#";
        vector<int> handCnt(26,0);
        for(char c: hand) handCnt[c-'A']++;
        int ans = solve(board, handCnt);
        return ans >= INF ? -1 : ans;
    }
};

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