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