题目描述

Hex 游戏在一个如下图所示菱形棋盘上进行，棋盘上的格子均为正六边形。

:::align{center} :::

两名玩家轮流行动。每回合，先手玩家在棋盘上放入一枚白棋，后手玩家在棋盘上放入一枚黑棋。如果白棋将棋盘的顶边与底边连接起来，则先手玩家获胜。如果黑棋将棋盘的左边与右边连接起来，则后手玩家获胜。两名玩家均随机落子：也就是说，若棋盘上有 $k$ 个空格，每个空格被选中的概率均为 $1/k$。给定一个已放置了部分棋子的棋盘，你的任务是计算每位玩家获胜的概率。注意，无论初始棋盘上有多少棋子，执白棋的玩家始终先手行动。

输入格式

第一行是测试数据的组数，最多不超过 20 组。对于每组测试数据，第一行是一个整数 $n$（$0 < n < 9$），表示棋盘的大小。接下来是描述棋盘状态的 $n$ 行，每行包含 $n$ 个非空格字符。其中 'W' 表示白棋，'B' 表示黑棋，'.' 表示空格。第 $i$ 行有 $i - 1$ 个前导空格，且相邻非空格字符之间有一个空格。每组测试数据之后有一个空行。

输出格式

对于每组测试数据，输出每位玩家的获胜概率，结果精确到 6 位小数。

2
4
. B W B
 B W B W
  W B W B
   . W B .

5
. B B . .
 B . B . .
  . B . B B
   . B B . .
    W W W W W

White 0.666667 Black 0.333333
White 0.000000 Black 1.000000

提示

翻译由 DeepSeek V4 Pro 完成