问题描述

你正在练习一种需要用到多个正方形瓷砖的杂耍。它们在大小上看起来都一样，但实际上有三种不同的瓷砖，分别为 A、B 和 X。通过瓷砖的质量可以区分它们的类型。同一种类型的瓷砖具有完全相同的质量。类型 A 瓷砖的质量范围在 \[mA1, mA2\] 内。类型 B 瓷砖的质量范围类似地在 \[mB1, mB2\] 内。对于类型 X 的瓷砖，质量恰好是 $mX$。

你得到了一个由瓷砖组成的大物体。瓷砖按照 $H \\times W$ 的网格排列。所有相邻的瓷砖都通过边缘粘在一起。$H \\times W$ 网格中的某些单元格可能为空。

你想要在杆子上平衡物体。然后你开始思考物体的重心。如果重心位于空单元格上，则无法将物体放在杆子上。每个单个正方形瓷砖的重心位于该正方形的中心。将具有质量 $m_{1}$ 和 $m_{2}$ 的两个物体组合起来后，重心是将两个重心之间的线段在内部按比例 $m_{2} : m_{1}$ 分割的点。

你的任务是编写一个程序，计算大物体重心实际位于物体上而不是物体中的空洞的概率。尽管未知类型 A 和 B 的确切质量，但概率遵循上述范围内的连续均匀分布。可以假设 A 和 B 之间的分布是独立的。

---

输入

输入的格式如下所示。

$H$ $W$ $mA1$ $mA2$ $mB1$ $mB2$ $mX$ $M_{1,1}M_{1,2}...M_{1,W}$ $M_{2,1}M_{2,2}...M_{2,W}$ : : $M_{H,1}M_{H,2}...M_{H,W}$

输入的第一行包含两个整数 $H$ 和 $W$ ($1 \\leq H, W \\leq 50$)，由一个空格分隔，其中 $H$ 和 $W$ 是给定矩阵的行数和列数。

输入的第二行包含五个整数 $mA1$、$mA2$、$mB1$、$mB2$ 和 $mX$ ($1 \\leq mA1 \\lt mA2 \\leq 100$, $1 \\leq mB1 \\lt mB2 \\leq 100$ 和 $1 \\leq mX \\leq 100$)，由一个空格分隔。

接下来的 $H$ 行，每行包含 $W$ 个字符，表示给定矩阵。在这些 $H$ 行中，A、B 和 X 分别表示类型 A、类型 B 和类型 X 的一块瓷砖， . 表示空单元格。在这些 $H$ 行中没有其他字符。

对于第 $i$ 行第 $j$ 列的单元格，其左上角坐标为 $(i, j)$，右下角坐标为 $(i+1, j+1)$。

你可以假设给定矩阵中至少有一个 A，B 和 X，并且所有的瓷砖都至少与一个边相连。此外，你可以假设物体重心的 x 坐标是整数的概率等于零，物体重心的 y 坐标是整数的概率也等于零。

输出

输出打印出物体重心位于物体上的概率。输出的误差不应大于 $10^{-8}$。

---

样例输入1

3 3
2 4 1 2 1
XAX
B.B
XAX

样例输入1对应的输出

0.0000000000000

---

样例输入2

4 2
1 100 1 100 50
AX
XB
BA
XB

样例输入2对应的输出

1.0

---

样例输入3

2 3
1 2 3 4 2
X.B
AXX

样例输入3对应的输出

0.500

---

样例输入4

10 10
1 100 1 100 1
AXXXXXXXXX
X........X
X........X
X..XXXXXXX
X........X
XXXXXX...X
X........X
X......X.X
X......X.X
XXXXXXXXXB

样例输入4对应的输出

0.4930639462354

---

样例输入5

25 38
42 99 40 89 3
...........X...............X..........
...........XXX..........XXXX..........
...........XXXXX.......XXXX...........
............XXXXXXXXXXXXXXX...........
............XXXXXXXXXXXXXXX...........
............XXXXXXXXXXXXXX............
.............XXXXXXXXXXXXX............
............XXXXXXXXXXXXXXX...........
...........XXXXXXXXXXXXXXXXX..........
.......X...XXXXXXXXXXXXXXXXX...X......
.......XX.XXXXXXXXXXXXXXXXXX..XX......
........XXXXXXXXXXXXXXXXXXXX.XX.......
..........XXXXXXXXXXXXXXXXXXXX........
.........XXXXX..XXXXXXXX..XXXXX.......
.......XXXXXX....XXXXX....XXXXXX......
......XXXXXXXX...XXXXX..XXXXXXXX.X....
....XXXXXXX..X...XXXXX..X..XXXXXXXX...
..BBBXXXXXX.....XXXXXXX......XXXAAAA..
...BBBXXXX......XXXXXXX........AAA....
..BBBB.........XXXXXXXXX........AAA...
...............XXXXXXXXX..............
..............XXXXXXXXXX..............
..............XXXXXXXXXX..............
...............XXXXXXXX...............
...............XXXXXXXX...............

样例输入5对应的输出

0.9418222212582

---

来源名称

Summer Camp 2013

---