题目描述

老师正在排座位，而且座位是随机排的。但是班里有两个人，只要他们 "相邻" 就说话。

这个班有 $n \times m$ 个座位，其中 . 表示空座位，# 表示不能坐的地方。

现在老师想知道排完座位后，这两个人说话的几率是多少？

注意，$\{(a,b),(c,d)\}$ 和 $\{(c,d),(a,b)\}$ 算作两种情况。

输入格式

第一行两个正整数 $n,m$，表示教室的行列数。

接下来 $n$ 行，每行 $m$ 个字符，表示每个座位能不能坐人。

输出格式

输出一个百分比，表示两人说话的几率，百分比保留五位小数。

6 8
........
........
........
........
........
#......#

15.26570%

数据范围与约定

对于 $50\%$ 的数据，$5 \le n,m \le 100$

对于 $100\%$ 的数据，$5 \le n,m \le 10^3$

$m\mod\ 3=2$

• 什么是 "相邻"？

  如果两人的座位八方向相接或两人是 "同桌"，则称两人 "相邻"。

• 什么是 "同桌"？

  如果一个人在第 $x$ 列且另一人在第 $x+2$ 列并在同一排，且不被过道隔开，则称两人为 "同桌"。

在列数（列数从1开始）$k\ \%\ 3=1$ 和 $k\ \%\ 3=2$ 中间有一条过道

注意，教室里的第一列和最后一列是单独的