C++ 版 2 人反转游戏

假设有两位玩家正在玩反转游戏。这里有一个仅包含以下两个字符的字符串：+ 和 -，玩家 1 和玩家 2 轮流将两个连续的“++”反转为“--”。当一名玩家无法再出招时游戏结束，另一名玩家将获胜。我们必须定义一个函数来检查起始玩家是否可以保证获胜。

因此，如果输入为 s = "++++"，则输出将为 true，因为起始玩家可以通过将中间的“++”反转为“+-+”来保证获胜。

要解决此问题，我们将遵循以下步骤 -

• 定义一个映射 memo

• 定义一个函数 solve()，它将带入 s，

• 如果 s 在 memo 中，则 -

  • 返回 memo[s]

• possible := false

• n := s 的大小

• 初始化 i := 0 时，当 i < n - 1 时，更新（将 i + 1），执行 -

  • 如果 s[i] 与 '+' 相同且 s[i + 1] 与 '+' 相同，则 -

    • s[i] := '-', s[i + 1] := '-'

    • possible := possible 或 solve(s) 的反转

    • s[i] := '+', s[i + 1] := '+'

    • 如果 possible 非零，则 -

      • 返回 memo[s] := possible

• 返回 memo[s] := possible

• 在主方法中执行以下操作 -

• 返回解决 (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

Arnab Chakraborty

更新于: 18-Nov-2020

249 次浏览

开启你的 职业

完成课程后获得认证

开始