SP14823 ABSHIP - Advanced Battleships

经过一番较量，你在战舰游戏中战胜了朋友，赢得了不少互联网积分！当然，这胜利绝对合法。然而，朋友对此感到不满，现在他挑战你进行一场重赛——这次是在高级战舰游戏中进行，并且赌注更高！ 在这场游戏中，你们各自拥有一个由 $M$ 行 $N$ 列组成的网格（$1 \leq M, N \leq 500$）。每个单元格要么空着，要么含有船只的一部分。游戏被称为“高级”，因为每艘船是由一个最大集合的一个或多个相邻非空单元格组成的。如果两个单元格共享一边，就算是相邻的。当然，每艘船之间不能有相邻的情况。 你知道可以通过告诉朋友有人证明了 P=NP 来分散他的注意力，但这招只能用一次。在他分心的时候，你会有机会用一只手抓住他的一些船只。你的手能覆盖一个 $S \times S$ 的正方形区域（$1 \leq S \leq \min\{M, N\}$），并可以一次性拿走所有至少部分位于该区域的船只。 当然，你的朋友并不简单，所以他把他的网格保护得非常好。因此，除网格大小外，你对其他一无所知。因此，到时候你只能随机选择网格内部的一个 $S \times S$ 区域。 如往常一样，这样的比赛吸引了很多观众。其中有一个旁观者，正好能看到你朋友的网格，他知道你的计划，并对你可能抓到的船只数量的期望值（即所有可能选择的平均船只数量）感到好奇。虽然他是个书呆子，但却不能心算出结果，因此他急忙去编写了一个程序……

第 1 行：3 个整数，分别是 $M$、$N$ 和 $S$ 接下来的 $M$ 行：每行由 $N$ 个字符组成，表示对手的网格——‘X’表示一艘船，‘.’表示一个空单元格。

输出一个数字，表示你能抓到的船只数量的期望值，结果保留 6 位小数。 **本翻译由 AI 自动生成**