मान लीजिए दो खिलाड़ी हैं जो फ्लिप गेम खेल रहे हैं। यहां हमारे पास एक स्ट्रिंग है जिसमें केवल ये दो वर्ण हैं:+ और -, खिलाड़ी 1 और खिलाड़ी 2 लगातार दो "++" को "-" में फ़्लिप करने के लिए ले जाते हैं। खेल तब समाप्त होता है जब एक खिलाड़ी आगे नहीं बढ़ पाता है और इसलिए दूसरा विजेता होगा। हमें यह जांचने के लिए एक फ़ंक्शन परिभाषित करना होगा कि क्या शुरुआती खिलाड़ी जीत की गारंटी दे सकता है।
इसलिए, यदि इनपुट s ="++++" जैसा है, तो आउटपुट सही होगा, क्योंकि शुरुआती खिलाड़ी "+--+" बनने के लिए मध्य "++" को फ़्लिप करके जीत की गारंटी दे सकता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मैप मेमो परिभाषित करें
-
फ़ंक्शन को हल करें () परिभाषित करें, इसमें s लगेगा,
-
अगर मेमो में है, तो -
-
वापसी मेमो[s]
-
-
संभव :=असत्य
-
n :=s का आकार
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
यदि s[i] '+' के समान है और s[i + 1] '+' के समान है, तो -
-
s[i] :='-', s[i + 1] :='-'
-
संभव:=संभव या हल के विपरीत
-
s[i] :='+', s[i + 1] :='+'
-
यदि संभव हो तो गैर-शून्य है, तो -
-
वापसी ज्ञापन [s] :=संभव
-
-
-
-
वापसी ज्ञापन [s] :=संभव
-
मुख्य विधि से निम्नलिखित करें -
-
वापसी समाधान(ओं)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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);
}
};
main(){
Solution ob;
cout << (ob.canWin("++++"));
} इनपुट
"++++"
आउटपुट
1