A19336.黑白方格

时间限制：2000ms
内存限制：512MB

给你一个 $N$ 行，$M$ 列的网格，其中每个方格都被涂成了 $\bf{黑色}$ 或者 $\bf{白色}$。

令 $S_{i,j}$ 表示每个方格的颜色，那么 $S_{i, j} =$ B 表示位于 $(i, j)$ 的方格为 $\bf{黑色}$；若 $S_{i, j} =$ W 表示方格为 $\bf{白色}$。

网格中上下左右相邻且颜色均为 $\bf{黑色}$ 的方格被称为属于同一个 $\bf{连通块}$。

具体地说：方格 $(a, b)$ 和方格 $(c, d)$ 属于同一个 $\bf{连通块}$ 当且仅当 $|a - c| + |b - d| = 1, S_{a, b} =$ B, $S_{c, d} =$ B。

求从网格上任选一个 $\bf{白色}$ 方格，将其涂为 $\bf{黑色}$ 后，网格中 $\bf{连通块}$ 数量的 $\bf{期望}$。

$\large{数据范围}$

• $1 \le N, M \le 1000$
• 题目保证至少有一个方格 $(i, j)$ 使得 $S_{i, j} =$ W。

对于每个测试用例格式如下：

$N$ $M$
$S_{1,1}$$S_{1,2}$$\ldots$$S_{1,M}$
$S_{2,1}$$S_{2,2}$$\ldots$$S_{2,M}$
$\vdots$
$S_{N,1}$$S_{N,2}$$\ldots$$S_{N,M}$

对于每个测试用例在单独的一行中输出答案；
输出答案与标准答案的绝对误差或相对误差不超过 $10^{−9}$，都会被视为正确答案。

对于第一个测试用例：

如果将方格 $(1,3)$ 重新涂成黑色，则黑色连通块的数量变为 $1$ 。

如果将方格 $(2,2)$ 重新绘制为黑色，则黑色连通块的数量变为 $1$ 。

如果将方格 $(3,2)$ 重新绘制为黑色，则黑色连通块的个数变为 $2$ 。

如果将方格 $(3,3)$ 重新绘制为黑色，则黑色连通块的个数变为 $2$ 。

因此，均匀随机选择一个白色方格并将其重新涂成黑色后，黑色连通块数量的期望值为 $(1+1+2+2)/4 = 3/2$ 。