C++ এ ফ্লিপ গেম II

ধরুন দুইজন খেলোয়াড় আছে যারা ফ্লিপ গেম খেলছে। এখানে আমাদের একটি স্ট্রিং রয়েছে যাতে শুধুমাত্র এই দুটি অক্ষর রয়েছে:+ এবং -, প্লেয়ার1 এবং প্লেয়ার2 পরপর দুটি "++" কে "--" এ ফ্লিপ করতে পালা করে। গেমটি শেষ হয় যখন একজন খেলোয়াড় আর নড়াচড়া করতে পারে না এবং তাই অন্য একজন বিজয়ী হবে। প্রারম্ভিক খেলোয়াড় জয়ের নিশ্চয়তা দিতে পারে কিনা তা পরীক্ষা করার জন্য আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে।

সুতরাং, যদি ইনপুটটি s ="++++" এর মত হয়, তাহলে আউটপুটটি সত্য হবে, কারণ প্রারম্ভিক খেলোয়াড় "+--+" হওয়ার জন্য মধ্যম "++" ফ্লিপ করে জয়ের নিশ্চয়তা দিতে পারে। পি>

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র মেমো সংজ্ঞায়িত করুন

• একটি ফাংশন সমাধান () সংজ্ঞায়িত করুন, এটি s,

  লাগবে

• যদি মেমোতে থাকে, তাহলে -

  • ফেরত মেমো[গুলি]

• সম্ভব :=মিথ্যা

• n :=s

  এর আকার

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি s[i] '+' এর মতো হয় এবং s[i + 1] '+' এর মতো হয়, তাহলে −

    • 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