第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
Treblecross游戏
Grade | Open Time | Friday, 19 September 2014, 10:07 am | |
Discount | 0.8 | Time Discount | Friday, 26 September 2014, 10:07 am |
Allow late | Yes | Close Time | Friday, 26 September 2014, 10:07 am |
Input file | treblecross.in | Output file | treblecross.out |
【题目描述】
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