C++ में फ्लिप गेम II - शुरुआती खिलाड़ी की जीत की गारंटी जांचें

समस्या विवरण

मान लीजिए दो खिलाड़ी फ्लिप गेम खेल रहे हैं। यहां हमारे पास एक स्ट्रिंग है जिसमें केवल ये दो वर्ण होते हैं: + और -। खिलाड़ी 1 और खिलाड़ी 2 बारी-बारी से दो लगातार "++" को "--" में फ्लिप करते हैं। खेल तब समाप्त होता है जब एक खिलाड़ी कोई चाल नहीं चल सकता और इसलिए दूसरा विजेता होगा। हमें एक फ़ंक्शन परिभाषित करना है जो जांचे कि क्या शुरुआती खिलाड़ी जीत की गारंटी दे सकता है।

उदाहरण के लिए, यदि इनपुट s = "++++" है, तो आउटपुट true होगा, क्योंकि शुरुआती खिलाड़ी बीच के "++" को फ्लिप करके "+--+" बनाकर जीत की गारंटी दे सकता है।

समाधान दृष्टिकोण

मेमोइजेशन के साथ DFS (मिनिमैक्स):

1. एक मैप memo परिभाषित करें
2. solve() फ़ंक्शन परिभाषित करें जो s लेता है:
   • यदि s memo में है, तो memo[s] लौटाएं
   • possible := false
   • n := s का आकार
   • i को 0 से n-2 तक लूप करें:
     • यदि s[i] == '+' और s[i+1] == '+':
       • s[i] := '-', s[i+1] := '-'
       • possible := possible OR NOT solve(s)
       • s[i] := '+', s[i+1] := '+' (बैकट्रैक)
       • यदि possible सत्य है, तो memo[s] := possible लौटाएं
   • memo[s] := possible लौटाएं
3. मुख्य विधि से: 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;
}

इनपुट

"++++"

आउटपुट

1