题目链接

填字母游戏

题目描述

在一个一维的格子条上，Alice 和 Bob 轮流填入字母 'L' 或 'O'。第一个成功构成连续子串 "LOL" 的玩家立即获胜。如果所有格子都填满仍未出现 "LOL"，则为平局。

给定一个包含 'L', 'O', '*' (空格) 的初始局面，你需要判断在 Alice 先手且双方都采取最优策略的情况下，最终的游戏结果。

解题思路

这是一个典型的组合游戏，其核心是找到最优策略。我们可以通过递归搜索所有可能的游戏进程，并用记忆化来优化，这本质上是一种动态规划（记忆化搜索）。

1. 状态定义

游戏中的任何一个局面都可以用一个字符串来唯一表示。我们的目标是判断在某个局面下，当前先手的玩家是必胜、必败还是只能平局。

2. 递归函数设计 (Minimax)

我们可以设计一个递归函数 dfs(state)，它的功能是判断在当前是 state 局面时，轮到当前玩家走，他能得到的最好结果是什么。我们定义返回值如下：

  • 1: 当前玩家有必胜策略。
  • 0: 当前玩家最好也只能逼平。
  • -1: 当前玩家必败。

3. 递归逻辑

  • 终止条件:
    • 对手已获胜: 检查当前 state 是否已经包含了 "LOL"。如果包含，说明上一个玩家（即当前玩家的对手）已经获胜，所以当前玩家必败。返回 -1。
    • 平局: 检查当前 state 是否已无空格 *。如果填满了且无人获胜，则为平局。返回 0。
  • 递归探索:
    • 遍历当前 state 中所有的空格 *。
    • 对于每个空格，尝试填入 'L' 和 'O'，形成一个新的局面 new_state。
    • 对 new_state 递归调用 dfs(new_state)。这个调用的返回值，是从对手的视角看的结果。
  • 结果判定:
    • 如果 dfs(new_state) 返回 -1，这意味着对手在 new_state 局面下必败。那么，这对于当前玩家来说就是一个必胜的走法。我们立即可以确定当前 state 是必胜的，返回 1。
    • 如果 dfs(new_state) 返回 0，这意味着对手可以逼平。这对于当前玩家来说，意味着他至少可以保证不输。我们记录下存在一个可以走向平局的策略。
    • 如果 dfs(new_state) 返回 1，这意味着对手必胜。这是一个对当前玩家不利的走法。
  • 最终返回:
    • 如果在遍历所有可能的走法后，我们找到了任何一个能让对手必败的走法，那么当前玩家必胜，返回 1。
    • 如果没有必胜走法，但至少有一个能逼平的走法，那么当前玩家的最好结果就是平局，返回 0。
    • 如果所有走法都会导向对手必胜的局面，那么当前玩家必败，返回 -1。

4. 记忆化

游戏中的同一局面可能通过不同路径到达。为了避免重复计算，我们使用一个 map (C++) / HashMap (Java) / dict (Python) 来存储已经计算过的 state 的结果。在 dfs 函数的入口处，首先检查当前 state 是否已经有结果，如果有则直接返回，这大大提高了算法效率。

代码

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

map<string, int> memo;

int dfs(string s) {
    if (memo.count(s)) {
        return memo[s];
    }

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

    int star_count = 0;
    for (char c : s) {
        if (c == '*') star_count++;
    }
    if (star_count == 0) {
        return memo[s] = 0;
    }

    bool can_tie = false;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '*') {
            s[i] = 'L';
            if (dfs(s) == -1) {
                s[i] = '*';
                return memo[s] = 1;
            }
            if (dfs(s) == 0) {
                can_tie = true;
            }
            s[i] = '*';

            s[i] = 'O';
            if (dfs(s) == -1) {
                s[i] = '*';
                return memo[s] = 1;
            }
            if (dfs(s) == 0) {
                can_tie = true;
            }
            s[i] = '*';
        }
    }

    if (can_tie) {
        return memo[s] = 0;
    } else {
        return memo[s] = -1;
    }
}

void solve() {
    string s;
    cin >> s;
    memo.clear();
    int result = dfs(s);
    if (result == 1) {
        cout << "Alice\n";
    } else if (result == 0) {
        cout << "Tie\n";
    } else {
        cout << "Bob\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<String, Integer> memo;

    static int dfs(String s) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }

        if (s.contains("LOL")) {
            memo.put(s, -1);
            return -1;
        }

        if (!s.contains("*")) {
            memo.put(s, 0);
            return 0;
        }

        boolean canTie = false;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '*') {
                chars[i] = 'L';
                int resL = dfs(new String(chars));
                if (resL == -1) {
                    chars[i] = '*';
                    memo.put(s, 1);
                    return 1;
                }
                if (resL == 0) {
                    canTie = true;
                }

                chars[i] = 'O';
                int resO = dfs(new String(chars));
                if (resO == -1) {
                    chars[i] = '*';
                    memo.put(s, 1);
                    return 1;
                }
                if (resO == 0) {
                    canTie = true;
                }
                
                chars[i] = '*'; // Backtrack
            }
        }

        int result = canTie ? 0 : -1;
        memo.put(s, result);
        return result;
    }

    public static void solve(Scanner sc) {
        String s = sc.next();
        memo = new HashMap<>();
        int result = dfs(s);
        
        if (result == 1) {
            System.out.println("Alice");
        } else if (result == 0) {
            System.out.println("Tie");
        } else {
            System.out.println("Bob");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
}

import sys

memo = {}

def dfs(s):
    if s in memo:
        return memo[s]

    if "LOL" in s:
        memo[s] = -1
        return -1

    if '*' not in s:
        memo[s] = 0
        return 0

    can_tie = False
    for i in range(len(s)):
        if s[i] == '*':
            # Try placing 'L'
            s_list = list(s)
            s_list[i] = 'L'
            new_s_l = "".join(s_list)
            res_l = dfs(new_s_l)
            if res_l == -1:
                memo[s] = 1
                return 1
            if res_l == 0:
                can_tie = True

            # Try placing 'O'
            s_list[i] = 'O'
            new_s_o = "".join(s_list)
            res_o = dfs(new_s_o)
            if res_o == -1:
                memo[s] = 1
                return 1
            if res_o == 0:
                can_tie = True

    result = 0 if can_tie else -1
    memo[s] = result
    return result

def solve():
    s = sys.stdin.readline().strip()
    global memo
    memo = {}
    
    # Python recursion limit can be an issue
    # The number of empty cells is max depth
    empty_cells = s.count('*')
    if sys.getrecursionlimit() < empty_cells + 5:
         sys.setrecursionlimit(empty_cells + 5)

    result = dfs(s)
    if result == 1:
        print("Alice")
    elif result == 0:
        print("Tie")
    else:
        print("Bob")

def main():
    t_str = sys.stdin.readline()
    if not t_str.strip():
        return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：记忆化搜索 (Minimax 动态规划)
  • 时间复杂度：，其中 是字符串的长度， 是从初始状态可达到的所有不同游戏局面的数量。由于记忆化的存在，每个局面只会被计算一次。在每次计算中，我们需要遍历字符串来寻找可落子的位置，成本为 。
  • 空间复杂度：，主要用于存储记忆化表的键（字符串）和值。递归的深度最多为棋盘上的空格数。