Problem C
Treblecross
Input: Standard Input
Output: Standard Output
Time Limit: 4 Seconds
Treblecross is a two player game where the goal is to get three X in a row on a one-dimensional board. At the start of the game all cells in the board is empty. In each turn a player puts a X in an empty cell, and if that results in there being three X next to each other, that player wins.
Given the current state of the game, you are to determine if the player to move can win the game assuming both players play perfectly. If so, you should also print all moves that will eventually lead to a win.
Consider the game where the board size is 5 cells. If the first player puts a X at position three (in the middle) so the state becomes ..X.., he will win the game as no matter where the other player puts his X, the first player can get three X in a row. If, on the other hand, the first player puts the X in any other position, the second player will win the game by putting the X in the opposite corner (for instance, after the second player moves the state might be .X..X). This will force the first player to put an X in a position so the second player wins in the next move.
Input
The input begins with an integer N (N<100), the number of states that will follow. Each state is represented by a string on a line by itself. The string will only contain the characters '.' and 'X'. The length of the string (the size of the board) will be between 3 and 200 characters, inclusive. No state will contain three X in a row.
Output
For each case, first output WINNING or LOSING depending on if the player to move will win or lose the game. On the next line, output in increasing order all positions on the board where the player to move may put an X and win the game. The positions should be separated by a blank, and be in increasing order. The leftmost position on the board is 1.
|
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 |
Problemsetter:
Jimmy Mårdell, Member of Elite Problemsetters' Panel