2017年第八届蓝桥杯 C++A组国赛第四题填字母游戏题解

本文主要是介绍2017年第八届蓝桥杯 C++A组国赛第四题填字母游戏题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考博客：蓝桥杯填字母游戏(博弈论)
OJ地址：填字母游戏

标题：填字母游戏

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：
“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。

K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。

并且：

轮到某人填的时候，只能在某个空格中填入L或O
谁先让字母组成了“LOL”的字样，谁获胜。
如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

本题的输入格式为：

第一行，数字n（n<10），表示下面有n个初始局面。
接下来，n行，每行一个串(长度<20)，表示开始的局面。
比如：“**”, 表示有6个空格。
“L****”, 表示左边是一个字母L，它的右边是4个空格。

要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。

1 表示能赢
-1 表示必输
0 表示可以逼平

例如，
输入：

4
***
L**L
L**L***L
L*****L

则程序应该输出：

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

20分代码（运行超时）

#include <bits/stdc++.h> using namespace std;typedef long long ll;int proc(string& s){int i;if(s.find("LOL")!=-1) return -1;if(s.find("*")==-1) return 0;int ans=-1;for(i=0;s[i];i++){if(s[i]=='*'){s[i]='L';ans=max(ans,-proc(s));if(ans==1){s[i]='*';return ans;}s[i]='O';ans=max(ans,-proc(s));
//          if(ans==1){     //在填O的时候进行特判会出错 s[i]='*';
//              return ans;//注意到，这是一道博弈论题，不是简单的dfs。 
//          }//小明的对手设定为最强，求解的是局面是否必败。对手只要有一种获胜组合，小明必败 }}return ans;
}int main(){
//  freopen("input.txt","r",stdin);int T;cin>>T;string s;while(T--){cin>>s;cout<<proc(s)<<endl;}return 0;
}