当前位置：网站首页>Leetcode 294. Flip game II (game theory)

Leetcode 294. Flip game II (game theory)

2022-07-03 00:39:00 【ccsu_ deer】

【 Title Description 】
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
Example:
        
         Input:
        
        
         1.
        
        
         s = "++++"
        
        
         1.
        
        
         Output: true 
         
Explanation: The starting player can guarantee a win by flipping the middle
        
        
         1.
         2.
        
        
         "++"
        
        
         1.
        
        
         to become
        
        
         1.
        
        
         "+--+"
        
        
         1.
        
        
         .
        
        
         1.
        
Follow up:
Derive your algorithm's runtime complexity.
practice ： The question was LC Lock the , You must be a member to watch , I use it here. C++ Let's do it . Combined with the last article ： Blog 
The solution to this problem is the current string If you reverse These two are continuous ++ Then the remaining state is If you are in a state of failure , This state is the winning state .
that dfs Just a second . What hurts is This question doesn't say the length of the string , So I dare not dfs Violent writing . After reading the solution, it is dfs Dare to write so .

       
        #include<bits/stdc++.h>
        
using namespace std;
        
const int N=1e2+10;
        
string s;
        
int run(string s)
        
{
        

        
    //cout<<s<<endl;
        
    for(int i=0;i<s.size();++i){
        
        if(i+1<s.size()&&s[i]=='+'&&s[i+1]=='+'
        
            &&!run(s.substr(0,i)+s.substr(i+2))) return 1;
        
    }
        
    return 0;
        
}
        
int main()
        
{
        
    cin>>s;
        
    if(run(s)) printf("First");
        
    else puts("Second");
        
    return 0;
        
}
        
/*
        
1100
        
*/
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.

原网站

版权声明
本文为[ccsu_ deer]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202151133028108.html

当前位置：网站首页>Leetcode 294. Flip game II (game theory)

Leetcode 294. Flip game II (game theory)

边栏推荐

猜你喜欢

随机推荐