3287: 网格图

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:2 解决:0

题目描述

小Q有一个n行n列的网格图,每个格子可能是空的(用’.’表示),也可能有障碍物(用’X’表示)。如果两个空格子有一个公共边,则称它们直接联通。如果两个空格子间存在一条由空格子组成的路径,且相邻两个空格子直接联通,则称这个两个空格子间接联通。
现在小Q得到了一个神器,这个神器可以消除原网格图中一个k*k的区域内的所有障碍物,使之变为空白格子。
小Q非常喜欢大的联通块,所以想知道,使用一次神器,能得到的最大联通块的大小是多少。(联通块是一个空白格子的集合,集合中任意两个空白格子都直接联通或间接联通)

输入

第一行两个整数n,k
接下来n行字符串,每个字符串包含n个字符,’.’表示空白,’X’表示有障碍物

输出

    输出最大联通块的大小

样例输入 复制

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

样例输出 复制

10

提示

    50%数据k<=n,n<=100
100%数据k<=n,n<=500