A Random Turn Connection Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7 Accepted Submission(s): 3
Problem Description
Alice and Bob play a random turn connection game in a square board with 8¡Á8 cells. In each move, a player tosses a fair coin to decide who gets the move. That is, both Alice and Bob will get the next move with 50% chance, no matter who has moved before. Once a player gets a move, she will place a piece in an empty cell. Both Alice and Bob play randomly. That is, if there are k empty cells, each cell will be chosen with 1/k chance. Once Alices pieces connect the top side and the bottom side of the board, she will win the game. Similarly, once Bobs pieces connect the left side and the right side of the board, he will win the game. Pieces only connect horizontally or vertically, and cannot connect diagonally. Your task is to calculate the winning probabilities of Alice and Bob.
Input
The first line is the number of test cases. Each test case contains 8 lines and each line contains 8 characters, representing the current status of the board. The cells occupied by Alice are marked as ¡°A¡±, the cells occupied by Bob are marked as ¡°B¡±, and the empty cells are marked as ¡°.¡±. There is an empty line between test cases.
Output
For each test case, output the probability that Alice and Bob will win with the precision of 6 digits.
Sample Input
4 ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... ....A... BBBB.BBB ....A... ....A... ....A... ....A... ....A... ....A... BBBBA... ...ABBBB ...A.... ...A.... ...A.... ........ ........ ........ ........ ........ ........ ........ .......A
Sample Output
Alice 1.000000 Bob 0.000000 Alice 0.500000 Bob 0.500000 Alice 0.000000 Bob 0.000000 Alice 0.223093 Bob 0.198498