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


【来源】

UVa10561 Treblecross

刘汝佳,《算法竞赛入门经典训练指南》表2.6