问题 5004 --虎哥的摧毁技能

5004: 虎哥的摧毁技能

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 5
[提交][状态][命题人:]

题目描述

给定一个n行n列的矩阵,每个格子里可能为空(用“.”表示)的也可能是障碍物(用“X”表示)。当相邻的格子都是空的,则称两个格子就是联通的,多个连通格子组成一个连通快。
虎哥拥有一个一次性的摧毁技能,该技能能够摧毁k*k矩形范围内的任何障碍物,使得这个范围内障碍物全部消失,变成是空的。使用该技能时,摧毁的矩形范围必须全部包含在给定矩阵内,超出给定矩阵的范围,则无法使用该技能。
请问在使用摧毁技能后,这个矩阵的最大连通块包含的格子的数量。

输入

第一行,两个整数n和k。(1≤k≤n≤500)
接下来n行,每行包含n个字符'.' 或者 'X',其中'.'表示该格子是空的,'X'表示该格子是封闭的。

输出

一个整数,表示最大连通块包含的格子的数量。
样例输入
Copy
5 2
..XXX
XX.XX
X.XXX
X...X
XXXX.
样例输出
Copy
10

提示

测试样例2:
输入:
5 3
.....
.XXX.
.XXX.
.XXX.
.....

输出:25


样例1解释如图所示:

来源

 

[提交][状态]