Problem F
Cracker Barrel Game
In this problem, you are giving a start position of between $1$ and $14$ pegs of different colors, as well as a target color. You should output whether it is possible to remove all but one peg from the board using the usual rules and end up with a peg that is of the target color.
Input
The input will contain up to $20$ test cases. Each test contains a target peg on a single line, followed by the initial position of the board. A peg is represented as a pair of two uppercase letters, e.g. BB represents a peg of a certain color (say blue). The board is given using appropriate indentation of $4$, $3$, $2$, and $1$ spaces for the $1^\text {st}$, $2^\text {nd}$, $3^\text {rd}$, and $4^\text {th}$ row.
The input will be terminated by a line containing the characters **.
Output
For each test case print Possible if there exists a sequence of valid moves such that all but one peg can be removed and you end up with a peg of the given target color. Otherwise, print Impossible.
| Sample Input 1 | Sample Output 1 |
|---|---|
BB
__
RR__
__YY__
____GG__
______WWBB
WW
__
RR__
__YY__
____GG__
______WWBB
BB
__
BBBB
BBRRRR
RRRRWWYY
WWWWYYBBRR
YY
__
BBBB
BBYYRR
RRRRWWBB
WWWWRRBBRR
BB
__
BBBB
YYYYYY
RRRR__BB
WW__RRBBRR
YY
__
BBBB
YYYYYY
RRRR__BB
WW__RRBBRR
**
|
Possible Impossible Possible Impossible Possible Impossible |
