| 题目名称 | 1486. [UVa 10561] Treblecross 游戏 |
|---|---|
| 输入输出 | treblecross.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-01-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：8， 通过率：62.5% | ||||
 _Horizon |
100 | 0.005 s | 0.32 MiB | C++ |
 KZNS |
100 | 0.008 s | 0.31 MiB | C++ |
 Aglove |
100 | 0.012 s | 0.32 MiB | C++ |
 炎帝 |
100 | 0.017 s | 0.31 MiB | C++ |
 cstdio |
100 | 0.023 s | 0.28 MiB | C++ |
|
Aglove |
80 | 0.016 s | 0.29 MiB | C++ |
|
Aglove |
20 | 0.010 s | 0.29 MiB | C++ |
|
Aglove |
20 | 0.010 s | 0.32 MiB | C++ |
| 关于 Treblecross 游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
不就是个三连消么……名字这么复杂……
| ||||
1486. [UVa 10561] Treblecross 游戏
★★ 输入文件：treblecross.in
输出文件：treblecross.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
$Treblecross$ 游戏是一种双人游戏，游戏在一个一行,$n$ 列的棋盘上进行。初始时所有的格子都是空的。两名玩家轮流向某个空格子中放置一个 $X$。如果此时有三个连续的 $X$ 出现，则该玩家获胜。
给出一个游戏的中间状态，计算先手是否必胜（假设两名玩家都执行最佳策略）。如果先手必胜，那么输出这一步的所有必胜策略。
考虑一个在 $1$ 行 $5$ 列棋盘上的 $Treblecross$ 游戏。如果第一名玩家把 $X$ 放在第三个（即中间的）格子中，那么状态变成了 ..$x$.. ，无论另一名玩家如何操作，他都能获胜。但如果第一名玩家把 $X$ 放在其他任何位置，另一名玩家都可以通过把 $X$ 放在棋盘另一边获胜（例如，在第二名玩家操作后状态可能变成.$X$..$X$）。在这种情况下，无论第一名玩家下一步进行什么操作，第二名玩家都能获胜。
【输入格式】
输入包含多组数据。
输入文件的第一行是一个正整数 $N(N<100)$，表示数据组数。
每组数据只有一行，是一个由'$X$'和'$.$'组成的字符串，其中'$.$'表示空格子。字符串长度（即棋盘的长度）在 $[3,200]$ 之间。保证不会有三个 $X$ 并排。
【输出格式】
对于每组数据，若先手必胜则首先输出"WINNING"，否则输出"LOSING"。
然后在第二行，按递增顺序输出先手的所有必胜策略，即先手下一步放X的位置。格子从左到右以 $1,2,3,...$ 编号。
【样例输入】
4 ..... X.....X..X.............X....X..X .X.X...X ...............................................
【样例输出】
WINNING 3 LOSING WINNING 3 WINNING 1 12 15 17 20 24 28 31 33 36 47
【来源】
刘汝佳，《算法竞赛入门经典训练指南》表2.6