P8658题解

Nightsky_Stars · 2023-12-21 20:15:59 · 题解

思路

递归 + 记忆化搜索，记忆化用 map 。

我们既然是和小明一伙的，所以肯定很希望小明输，所以能胜就胜，不能就平，否则才败。

每次就判断一下小明是否胜利及是否有未填的空位，再循环遍历一下，如果该位置为空位，就尝试将 L 和 O 填入空位，看看能不能赢。

CODE:

#include<bits/stdc++.h>
using namespace std;
map<string,int> m;
string s;
int check(){
    if(m.count(s)) return m[s];
    if(s.find("LOL")!=-1) return -1;
    if(s.find('*')==-1) return 0;
    bool res=false;
    for(int i=0;s[i];i++){
        if(s[i]=='*'){
            s[i]='L';
            int ans=check();
            s[i]='*';
            if(ans==-1) return m[s]=1;
            else if(ans==0) res=true;
            s[i]='O';
            ans=check();
            s[i]='*';
            if(ans==-1) return m[s]=1;
            else if(ans==0) res=true;
        }
    }
    if(res) return m[s]=0;
    return m[s]=-1;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        if(s.length()<3){
            cout<<"0"<<endl;
            continue;
        }
        cout<<check()<<endl;
    }
    return 0;
}