A Random Turn Connection Game

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.

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.

For each test case, output the probability that Alice and Bob will win with the precision of 6 digits.

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

Alice 1.000000 Bob 0.000000
Alice 0.500000 Bob 0.500000
Alice 0.000000 Bob 0.000000
Alice 0.223093 Bob 0.198498

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）