50 - ZOJ Monthly, February 2006 - 1006
Military Game is a little funny game that can be found as early as 1882. It was (last) popularized by Martin Gardner in 1963. The game is played by two players as thrown in Figure 1, one controlling the three black pieces while the other controls the remaining red piece. The players alternate to move their pieces, the Red piece can move to any adjacent cell, the Black pieces can only move 'up' or 'sideways', but can not go in a backward (downward) direction. Black wins by trapping Red so that the Red piece can not move, shown as Figure 2. Red wins by either escaping to the bottom cell, or if Black makes 10 passive (non-advancing) moves in a row. Initially, the pieces are placed as Figure 3, and Black goes first. Your task is given a configuration of the game, then determine whether Black has a winning strategy.
The input consists of multiple lines, and each represents a game configuration in the format "R B1 B2 B3 T", where R, B1, B2 and B3 are the cell indices as shown in Figure 4 specifying the position of the Red piece and the Black pieces, respectively, and T is a character which is either 'r' or 'b' specifying next player to move the pieces, 'r' for Red and 'b' for Black. The input ends with EOF.
For each game configuration, print a single line to describe whether Black has a winning strategy, if Black can always trap the Red starting from the configuration, print out "Win", and if the Red the can escape, then print out "Lose". You may assume the game never draws according to the rule. If the given configuration is not reachable from the initial configuration, print out "Impossible".
1 2 3 4 r 1 2 6 4 b 1 2 3 6 r 6 8 11 10 b 6 8 9 10 r 1 2 4 4 b 11 11 10 9 b
Win Win Lose Win Win Impossible Impossible
Author: YANG Chao