สมมติว่ามีผู้เล่นสองคนเล่น flip game นี่คือสตริงที่มีแค่สองตัวอักษร: + และ - player1 และ player2 สลับกันพลิก "++" ติดกันสองตัวเป็น "--" เกมจบเมื่อผู้เล่นคนหนึ่งไม่สามารถเล่นได้อีก และอีกคนจะเป็นผู้ชนะ เราต้องกำหนดฟังก์ชันตรวจสอบว่าผู้เล่นเริ่มต้นสามารถรับประกันชัยชนะได้หรือไม่
เช่น ถ้าอินพุทเป็น s = "++++" ผลลัพธ์จะเป็น true เนื่องจากผู้เล่นเริ่มต้นสามารถรับประกันชัยชนะได้โดยการพลิก "++" กลางให้กลายเป็น "+--+"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดแมป memo
กำหนดฟังก์ชัน solve() รับ s
ถ้า s อยู่ใน memo แล้ว −
คืนค่า memo[s]
possible := false
n := ขนาดของ s
ลูป i := 0 ถึง n - 2 ทำ −
ถ้า s[i] เป็น '+' และ s[i + 1] เป็น '+' แล้ว −
s[i] := '-', s[i + 1] := '-'
possible := possible OR ค่าตรงข้ามของ solve(s)
s[i] := '+', s[i + 1] := '+'
ถ้า possible ไม่เป็นศูนย์ แล้ว −
คืนค่า memo[s] := possible
คืนค่า memo[s] := possible
จากเมธอดหลักทำดังนี้ −
คืนค่า solve(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
