【蓝桥杯】43695.填字母游戏

题目描述

小明经常玩 LOL 游戏上瘾，一次他想挑战 K 大师，不料 K 大师说：

“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩 LOL 了”。

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

并且：

轮到某人填的时候，只能在某个空格中填入 L 或 O。

谁先让字母组成了"LOL"的字样，谁获胜。

如果所有格子都填满了，仍无法组成 LOL，则平局。

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

输入描述

本题的输入格式为：

第一行，数字 n（n<10），表示下面有 n 个初始局面。

接下来，n 行，每行一个串，表示开始的局面。

比如：“$\ast \ast \ast \ast \ast \ast$”, 表示有 6 个空格。“$L\ast \ast \ast \ast$”, 表示左边是一个字母 L，它的右边是 4 个空格。

输出描述

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

1 表示能赢；

-1 表示必输；

0 表示可以逼平。

输入输出样例

示例
输入

4
$\ast \ast \ast$
$L\ast \ast L$
$L\ast \ast L\ast \ast \ast L$
$L\ast \ast \ast \ast \ast L$

输出

0
-1
1
1

题目解析

  如果我们玩过五子棋或者XO棋，那么对于这个游戏来说其实就不算陌生，本质上来说，五子棋、XO棋和填字母的核心算法都差不多。
  在已知初始状态，求结束状态的算法中，无非就是枚举或者遍历，来求得局面的每一种可能性，然后将符合条件的可能性局面筛选出来。如果可能的局面数量比较少，那么枚举足以；如果可能的局面数量比较多，那么就需要使用深度优先算法DFS 或者 广度优先算法BFS 来一边遍历一边筛选了。
  在这道题中，已知初始局面，问结束局面中能够有赢的可能性，我们可以选用深度优先算法DFS来解决。
  以 $L\ast \ast L$ 来举例：
  首先，读取并保存初始状态，并设置一个flag标志，默认为最坏的情况，为必输-1；
  然后，尝试在空格的位置填入 “L” 或者 “O” ，比如填入 “L” ，这样就可以得到一个新的局面 $LL\ast L$ 或者 $LO\ast L$，遍历这个字符串，这个局面中没有可以形成 “$LOL$” 的 片段 ；
  接着由对面填字，将这个新片段加入队列 ，然后尝试递归调用继续搜索新局面，在新的局面中，会有 $LLOL$ 或者 $LOLL$ 的状态，都满足"$LOL$" 的 片段的获胜条件，那么对于小明来说，他就面临必输的局面。
  相反，如果是在小明填字完成后，形成了"$LOL$" 的 片段，则小明有获胜的希望，将flag = 1。
  如果所有的空格都被填满后，仍然无法形成"$LOL$" 的 片段，则判为平局，将flag = 0。

算法流程

1. 输入处理：首先读取一个整数 n，表示有 n 个初始局面。然后通过循环读取 n 个字符串，每个字符串表示一个初始局面。
2. 深度优先搜索（DFS）：dfs 函数用于模拟游戏过程，通过递归的方式尝试所有可能的填法。在递归过程中，使用字典 di 记录已经计算过的局面状态及其结果，避免重复计算。
3. 胜负判断：在 dfs 函数中，根据当前局面是否出现 “LOL”、“L*L”、“OL”、“LO”
   以及是否还有空位等情况，判断当前局面的胜负或平局。
4. 填字母尝试：对于当前局面中的每个空位，分别尝试填入 “L” 和 “O”，并递归调用 dfs 函数获取下一轮的结果。根据下一轮的结果更新当前局面的最好结果。
5. 输出结果：对于每个初始局面，调用 dfs 函数计算并输出小明的最好结果（1 表示能赢，-1 表示必输，0 表示可以逼平）。

代码展示

感谢 @殷允贺 同学提供的代码。在其基础上添加了部分注释内容。

import os
import sys

# 读取输入的局面数量 n ，表示下面有 n 个初始局面
n = int(input())  

# 定义深度优先搜索函数，用于模拟游戏过程并判断当前局面下的胜负情况
def dfs(s, n):
    # 1. 判断当前局面状态是否已经在字典中记录过
    # 如果已经记录过，直接返回该状态对应的结果，避免重复计算
    if s in di.keys():
        return di[s]
    
    # 2. 判断当前局面是否可直接判断出胜负
    # 如果当前局面中已经出现了 "LOL"，说明在之前的步骤中对方已经完成了 "LOL" 的组合，当前玩家输了
    if "LOL" in s:
        di[s] = -1
        return -1  # 表示输
    
    # 如果当前局面中出现了 "L*L" 或者 "*OL" 或者 "LO*"，说明当前玩家可以通过在空位填入合适的字母（L 或 O）组成 "LOL"，当前玩家赢了
    elif "L*L" in s or "*OL" in s or "LO*" in s:
        di[s] = 1
        return 1  # 表示赢
    
    # 如果当前局面中没有空位（即没有 "*"），且也没有出现 "LOL"，说明所有格子都填满了仍未组成 "LOL"，形成平局
    elif "*" not in s and "LOL" not in s:
        di[s] = 0
        return 0  # 表示平局
    
    # 初始化一个标志变量 flag，用于记录当前局面的最好结果，在初始化时考虑最差的情况，默认为无论怎么选，小明都只能输
    flag = -1  

    # 遍历当前局面的每一个位置，看是否能改变局面得到更好的结果
    for i in range(n):
        # 由于字符串是不可变类型，不能直接修改，所以将字符串转换为列表
        ls = list(s)  

        # 只有当前位置是空位（即 "*"）时，才能填入字母
        if ls[i] == "*":
            # 情况 1：在当前空位填入字母 "L"
            ls[i] = 'L'
            # 将修改后的列表转换回字符串，并递归调用 dfs 函数，获取上一轮的结果
            last_r1 = dfs("".join(ls), n)  

            # 如果上一轮的结果是 -1，说明在填入 "L" 后，对方的局面是输，那么当前玩家（小明）可以赢
            if last_r1 == -1:
                di[s] = 1
                return 1  # 表示赢
            
            # 如果上一轮的结果是 0，说明在填入 "L" 后，局面是平局，那么小明至少可以逼平
            if last_r1 == 0:
                flag = 0

            # 情况 2：在当前空位填入字母 "O"
            ls[i] = 'O'
            # 将修改后的列表转换回字符串，并递归调用 dfs 函数，获取上一轮的结果
            last_r2 = dfs("".join(ls), n)

            # 如果上一轮的结果是 -1，说明在填入 "O" 后，对方的局面是输，那么当前玩家（小明）可以赢
            if last_r2 == -1:
                di[s] = 1
                return 1  # 表示赢
            
            # 如果上一轮的结果是 0，说明在填入 "O" 后，局面是平局，那么小明至少可以逼平
            if last_r2 == 0:
                flag = 0

    # 把 flag 作为当前局面的对局结果记录到字典中
    di[s] = flag
    # 最终返回当前局面的对局结果
    return di[s]

# 处理 n 个局面的初始状态
for i in range(n):
    # 每次处理一个新局面时，初始化一个空字典，用于记录该局面下每一种独立状态及其对应的对局结果
    di = {}
    # 读取当前局面的起始状态
    s = input()
    # 调用 dfs 函数计算并输出当前局面下小明的最好结果
    print(dfs(s, len(s)))