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