← 返回题目列表

Codeforces · 57/D

D. 旅程

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

兔子 Stewie 探索一个新的平行宇宙。这个二维宇宙具有矩形网格的形状,包含n行和m列。宇宙非常小:网格的一个单元只能包含一个粒子。这个宇宙中的每个粒子要么是静态的,要么是动态的。每个静态粒子始终保持在一个相同的位置。由于难以理解的引力定律,平行宇宙中的两个静态粒子不能出现在一列或一行中,它们也不能出现在对角相邻的单元中。动态粒子出现在随机的空单元格中,随机选择目标单元格(目标单元格可能与起始单元格重合,请参阅示例)并沿着穿过单元格的最短路径移动到那里,不被静态粒子占据。所有空单元格被选为路径起点或终点的概率相同。到达目标单元格后,粒子就会消失。某一时刻只能存在一个动态粒子。如果它们有相邻的一侧,则该粒子可以从一个细胞移动到另一个细胞,并且这种转变恰好需要一银河秒。斯蒂威对给定宇宙中一个粒子的平均寿命感兴趣。

输入

第一行包含两个空格分隔的整数:n, m (2 ≤ n, m ≤ 1000),它们代表宇宙的大小。接下来的 n 行包含 m 个符号,每个符号描述没有动态粒子的宇宙 - 如果单元格被静态粒子占据,则第 i 行的第 j 个符号等于“X”,并且等于“.”。如果它是空的。保证所描述的宇宙满足上述性质,即没有两个静态粒子可以在一列或一行中,并且它们不能位于对角相邻的单元中。

输出

您必须在一行上打印一个数字,该数字是粒子的平均寿命,精确度至少为小数点后 6 位。

如果答案与正确答案的绝对或相对误差在 10 - 6 以内,则答案将被接受。

示例

输入 #1

2 2
..
.X

输出 #1

0.888888888889

输入 #2

3 3
...
.X.
...

输出 #2

2.000000000000