← 返回题目列表

Codeforces · 679/C

C. 熊和方格

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

您有一个包含 n 行和 n 列的网格。每个单元格要么是空的(用“.”表示),要么是阻塞的(用“X”表示)。

如果两个空单元共享一侧,则直接连接。如果存在以 (r1, c1) 开始、以 (r2, c2) 结束的空单元序列,且该序列中任意两个连续的单元直接相连,则两个单元 (r1, c1)(位于 r1 行和 c1 列)和 (r2, c2) 相连。连接组件是一组空单元,组件中的任何两个单元都连接,并且该组中没有单元连接到不在该组中的某个单元。

你的朋友 Limak 是一只大灰熊。他能够摧毁一定范围内的任何障碍。更准确地说,您可以在网格中选择一个大小为 k × k 的正方形,Limak 会将其中所有被阻挡的单元格转换为空单元格。但是,您只能请求 Limak 提供一次帮助。

所选方块必须完全位于网格内。利马克可能不会改变任何东西,因为无论如何所有单元格都是空的。

您喜欢大型连接组件。在 Limak 帮助您之后,网格中最大连通分量的最大可能尺寸是多少?

输入

输入的第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 500)——分别是网格的大小和 Limak 的范围。

接下来的 n 行中的每一行都包含一个包含 n 个字符的字符串,表示网格的第 i 行。每个字符都是“.”或“X”,分别表示空单元格或阻塞单元格。

输出

使用 Limak 的帮助后,打印最大连通分量的最大可能大小(单元格数量)。

示例

输入 #1

5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.

输出 #1

10

输入 #2

5 3
.....
.XXX.
.XXX.
.XXX.
.....

输出 #2

25

注意

在第一个示例中,您可以选择大小为 2 × 2 的正方形。最好选择下图左图红框中的正方形。然后,您将得到一个包含 10 个单元的连接组件,在右图中标记为蓝色。