AT_icpc2013autumn_i Overwriting Game
题目描述
# 覆写游戏
## 题目背景
你有一个 $H$ 行 $W$ 列的矩形板。行从上到下被编号为 $1$ 到 $H$ 行，列从左到右被编号为 $1$ 到 $W$ 列。$i$ 行 $j$ 列处的方格用 $(i,j)$ 表示。方格只有 $2$ 种颜色：白和黑。
你将按如下方法给矩形板涂色：
1. 等概率随机选择一个方格 $(i,j)$ 和一种颜色 $c$。$(1≤i≤H,1≤j≤W,c∈\{Black,White\})$
1. 给每一组满足$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