← 返回题目列表

AtCoder · icpc2013summer_day4_h

H. 重力点

中文机器翻译题面 查看原题

问题陈述

您正在练习涉及多个方形瓷砖的杂耍。 它们的大小看起来都一样,但实际上有三种不同的瓷砖:A、B 和 X。 瓷砖的种类可以通过其质量来区分。 所有同类瓷砖的质量完全相同。 A型瓷砖的质量在范围内 [mA1, mA2]。 B 型瓷砖的质量同样在范围内 [mB1, mB2]。 您不知道 A 型和 B 型的确切数字。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 坐标为整数的概率等于 0,并且对象的重心的 y 坐标为整数的概率等于 0。

输出

打印物体重心位于物体上的概率。 输出不应包含大于 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