覆写游戏

题目背景

你有一个 $H$ 行 $W$ 列的矩形板。行从上到下被编号为 $1$ 到 $H$ 行，列从左到右被编号为 $1$ 到 $W$ 列。$i$ 行 $j$ 列处的方格用 $(i,j)$ 表示。方格只有 $2$ 种颜色：白和黑。

题目描述

你将按如下方法给矩形板涂色：

1. 等概率随机选择一个方格 $(i,j)$ 和一种颜色 $c$。$(1≤i≤H,1≤j≤W,c∈\{Black,White\})$
2. 给每一组满足$1≤i'≤i,1≤j'≤j$的 $(i',j')$ 所表示的方格涂上颜色 $c$。

以下是一次涂色操作的例子。你有一个 $3×4$ 的矩形板，颜色如下图左侧所示。如果你随机选择了方格 $(2,3)$ 和颜色 $Black$，涂色后矩形板将如下图右侧所示。$6$ 个方格被涂了色。

现在我们数出被涂色的方块数量，即使他们的颜色没有改变，如上图中的 $(1,2)$。

给出矩形板的初始着色和目标着色，你要不停重复地进行涂色操作直到矩形板变为目标着色。

求在这些涂色操作中被涂色的方块总数的期望值。

输入格式

输入包含至多 $100$ 组数据。

在每组数据中：

第 $1$ 行包含两个整数 $H,W$。

随后给出两个颜色构造，分别为初始着色和目标着色。

每个颜色构造由 $H$ 行，每行 $W$ 个字符组成。字符只能为 B 或 W，分别表示黑色和白色。

在两个颜色构造之间和两组数据之间都有空行间隔。

输入以0 0结束，你不应将它们作为一组数据处理。

输出格式

对于每一组数据，输出一行对应的期望值。绝对误差与相对误差不能超过 $10^{-6}$。

输入输出样例

输入 #1

1 2
BB

WW

2 1
B
W

B
W

2 2
BW
BW

WW
WW

3 4
BBBB
BBBB
BBBB

WWWW
WWWW
WWWW

5 5
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB

BBBBB
BBBWB
BBBBB
BWBBB
BBBBB

0 0

输出 #1

6.0000000000
0.0000000000
12.8571428571
120.0000000000
23795493.8449918639

说明/提示

【数据范围与约定】

对于 $100\%$ 的数据，$1≤H,W≤5$。

数据保证答案均不超过 $10^9$。

Translate by Georiky