플립 게임을 하는 두 명의 플레이어가 있다고 가정합니다. 여기에 + 및 -의 두 문자만 포함된 문자열이 있습니다. player1과 player2는 교대로 두 개의 연속 "++"를 "--"로 뒤집습니다. 한 플레이어가 더 이상 움직일 수 없을 때 게임이 종료되므로 다른 플레이어가 승자가 됩니다. 시작 플레이어가 승리를 보장할 수 있는지 확인하는 함수를 정의해야 합니다.
따라서 입력이 s ="++++"와 같으면 시작 플레이어가 중간 "++"를 "+--+"로 뒤집음으로써 승리를 보장할 수 있으므로 출력은 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 지도 메모 정의
-
solve() 함수를 정의하면 s가 소요됩니다.
-
메모에 s가 있으면 -
-
회신 메모[s]
-
-
가능 :=거짓
-
n :=s
의 크기 -
initialize i :=0의 경우, i
-
s[i]가 '+'와 같고 s[i + 1]이 '+'와 같으면 -
-
s[i] :='-', s[i + 1] :='-'
-
가능 :=가능 또는 해결의 역
-
s[i] :='+', s[i + 1] :='+'
-
가능한 경우 0이 아닌 경우 -
-
회신 메모[s] :=가능
-
-
-
-
회신 메모[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