记忆化搜索博弈树

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int n,len;

unordered_map<string,int> vis;//记录这种局面是否访问过和这种局面的结果 

string str;

int boyi(){

if(vis.count(str)==1){

return vis[str];

} 

if(str.find("LOL")!=string::npos){vis[str]=-1;return -1;}

if(str.find("*")==string::npos){vis[str]=0;return 0;}

//已经没有空格了，但仍没有出现LOL，平了 

if(str.find("*OL")!=string::npos||

   str.find("L*L")!=string::npos||

   str.find("LO*")!=string::npos){vis[str]=1;return 1;}

int res=-1;

bool flag=0;

for(int i=0;i<len;i++){

if(str[i]=='*'){

str[i]='L';

res=boyi();

str[i]='*';

if(res==-1){vis[str]=1;return 1;}

if(res==0)flag=1;

str[i]='O';

res=boyi();

str[i]='*';

if(res==-1){vis[str]=1;return 1;}

if(res==0)flag=1;

}

}

if(flag){vis[str]=0;return 0;}

vis[str]=-1;return -1;

}

int main(){

ios::sync_with_stdio(false);

cin>>n;

while(n--){

cin>>str;

len=str.length();

cout<<boyi()<<endl;

}

return 0;

}