填字母游戏
小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。
并且：
轮到某人填的时候，只能在某个空格中填入L或O。谁先让字母组成了“LOL”的字样，谁获胜。如果所有格子都填满了，仍无法组成LOL，则平局。
小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。
本题的输入格式为：
第一行，数字n（n<10），表示下面有n个初始局面。接下来，n行，每行一个串，表示开始的局面。
比如：“******”, 表示有6个空格。 “L****”, 表示左边是一个字母L，它的右边是4个空格。要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。1 表示能赢-1 表示必输0 表示可以逼平
例如，
输入：
4***L**LL**L***LL*****L
则程序应该输出：
0
-1
1
1
思路：
这到题是博弈题我们可以用一个字典把之前知道的结果存储起来，以便减少深搜的时间复杂度，减少程序运行时间。博弈问题形式基本就是前面的框架是判断输赢的条件，for就是遍历各种走法，一直使得小明为最好的结果。if s in d:就是判断是否之前知道最优解。但蓝桥杯只能通过60分。
程序：
def me(w):global ds="".join(w)if s in d:return d[s]if s.count("LOL")>0:return -1if len(s)<3 or s.count("*")==0: return 0c=-1for i in range(0,len(w)):if w[i]=="*":try:w[i]="L"#试着填Lc=max(c,-me(w))if c==1:breakelse:w[i]="O"#试着填Oc=max(c,-me(w))if c==1:breakfinally:w[i]="*"#回溯s="".join(w)d[s]=creturn cw=int(input())w1=[input() for i in range(w)]for i in w1:d={}print(me(list(i)))
禁止转载。仅用于自己学习。对程序错误不负责。
