C ++中的Flip Game II
假设有两个玩家在玩翻页游戏。在这里，我们有一个仅包含以下两个字符的字符串：+和-，player1和player2轮流将两个连续的“++”翻转为“-”。当一个玩家不再能够移动时，游戏结束，因此另一位玩家将成为获胜者。我们必须定义一个函数来检查起始玩家是否可以保证获胜。
因此，如果输入类似于s=“++++”，那么输出将为true，因为起始玩家可以通过将中间的“++”翻转为“+-+”来保证获胜。
为了解决这个问题，我们将遵循以下步骤-
定义一个映射备忘录
定义一个函数solve()，需要s，
如果在备忘录中，则-
返回备忘录
可能：=假
n：=s的大小
对于初始化i：=0，当i<n-1，更新（将i增加1）时，执行-
s[i]：='-'，s[i+1]：='-'
可能的：=可能的OR或逆
s[i]：='+'，s[i+1]：='+'
如果可能为非零，则-
返回备忘录：=可能
如果s[i]与'+'相同，而s[i+1]与'+'相同，则-
返回备忘录：=可能
从主要方法中执行以下操作-
返回求解
例
让我们看下面的实现以更好地理解-
#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