C++-এ Flip Game II: ফ্লিপ গেমে শুরুতেই জয় নিশ্চিত করা সম্ভব কিনা

দুই খেলোয়াড় একটি ফ্লিপ গেম খেলছে। একটি স্ট্রিং আছে যা শুধু '+' এবং '-' দিয়ে গঠিত। খেলোয়াড়রা পালা পালায় দুটি সতত "++" কে "--" এ ফ্লিপ করে। kiam এক খেলোয়াড় আর মুভ দিতে না পারে, তবে অন্যটি জিতবে। যাচাই করতে হবে শুরুর খেলোয়াড় জয় নিশ্চিত করতে পারে কিনা।

উদাহরণ

ইনপুট: s = "++++"

আউটপুট: true

ব্যাখ্যা: শুরুর খেলোয়াড় মাঝপথের "++" কে "--" এ ফ্লিপ করে "+--+" বানাতে পারে, যা প্রতিপক্ষকে হারায়।

সমাধানের পদ্ধতি (Recursion + Memoization / Game Theory)

মেমোরাইজেশনের জন্য unordered_map memo।
রিকারসিভ ফাংশন solve(s):
- যদি s মেমোতে থাকে, তবে রিটার্ন করুন।
- possible = false।
- স্ট্রিং স্ক্যান করুন i = 0 থেকে n-2:
  - যদি s[i] == '+' && s[i+1] == '+':
    - সেটাকে "--" করুন।
    - possible |= !solve(s) (প্রতিপক্ষ হারালে আমি জিতি)।
    - ব্যাকট্র্যাক (ফিরিয়ে দিন "++")।
    - যদি possible হয়ে যায়, তবে আংশিক ফলাফল মেমোতে সেভ করে রিটার্ন করুন।
- memo[s] = possible রিটার্ন করুন।
মেইন থেকে solve(s) কল করুন।

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] = possible;
            }
        }
        return memo[s] = possible;
    }
    
    bool canWin(string s) {
        return solve(s);
    }
};

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

ইনপুট

"++++"