OI题库

【题目描述】

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