ZOJ Problem Set - 3047
Connect Four is a game which players take turns putting their pieces on the gameboard, and whoever first gets four of his pieces in a row wins, the four could be in a row vertically, horizontally or diagonally. The gameboard is 7*7, and there are 7 slots(a slot is a column of the gameboard) in the game into which the players can put their pieces, a piece will lands at the bottom of the slot if the slot is empty or lands on the previous topmost piece in that slot. Of course, a player cannot put his piece into a slot that is already full. Assume the player with the piece '*' goes first, given a gameplay situation, determine whether in 2(each player's move is counted as one move) moves or less one of the players has a winning strategy (assuming both players know their best possible strategy) or a player had already won with the last move.
Output "Impossible" if the situation given is impossible(that there cannot be such a state of game), or "* Wins" if the player with the piece '*' wins, or "o Wins" if the player with the piece 'o' wins, or "Neither Wins" if a winning strategy is not possible for either players. The situation can be impossible because of many reasons. To simplify it a little, if all the pieces are placed correctly and the number of each kind of pieces is legal, you can always assume that the pieces of the situation can be put into the gameboard alternatively.
The first line of the input is T(T<=100) then T blocks follow, each block is a gameplay situation '*' means a piece of the '*' player, 'o' means a piece of the o player and 'x' means a place not occupied. There is a blank line after each input block.
Output the result as described.
2 xxxxxxx xxxxxxx xxxxxxx xxxxxxx o*xxxxx oo*xxx* ooo**** xxxxxxx xxxxxxx xxxxxxx *xxxxxx o*xxxxx oo*xxxx ooo**xx
* Wins Impossible
Author: SONG, Yu
Source: ZOJ Monthly, October 2008