Flip Game II - Người chơi đầu tiên có thắng chắc không?

Hai người chơi luân phiên đổi "++" thành "--" trong chuỗi. Người không còn nước đi thì thua. Kiểm tra người chơi đầu có chiến lược thắng chắc không.

Ví dụ: "++++" → true (đổi giữa thành "+--+").

Giải thuật (Minimax + Memoization)

Duyệt mọi vị trí "++", thử đổi, đệ quy kiểm tra đối thủ có thua không (!solve(newState)). Nếu có nước đi khiến đối thủ thua → trạng thái hiện tại thắng. Dùng memo (unordered_map) lưu kết quả chuỗi đã tính.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    unordered_map<string, bool> memo;

    bool solve(string s) {
        if (memo.count(s)) return memo[s];
        bool possible = false;
        int n = s.size();
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                s[i] = s[i+1] = '-';
                possible |= !solve(s);
                s[i] = s[i+1] = '+';
                if (possible) return memo[s] = true;
            }
        }
        return memo[s] = possible;
    }

    bool canWin(string s) {
        return solve(s);
    }
};

int main() {
    Solution ob;
    cout << ob.canWin("++++");
    return 0;
}

Đầu vào

"++++"

Đầu ra

1