#P3135. [USACO16JAN] Fort Moo P

    ID: 2174 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划,dp2016USACO枚举,暴力构造

[USACO16JAN] Fort Moo P

Description

Bessie 正在和她的朋友 Elsie 一起建造一个堡垒。像任何好的堡垒一样,这个堡垒需要一个坚固的框架。Bessie 想要建造一个一米宽的矩形轮廓框架,然后在这个框架上建造堡垒。

Bessie 已经选择了一个建造堡垒的地点——一块 NN 米乘 MM 米的土地(1N,M2001 \leq N, M \leq 200)。不幸的是,这块地有一些沼泽区域,不能用来支撑框架。请帮助 Bessie 确定她可以用堡垒覆盖的最大面积(由框架支撑的矩形的面积),使得框架不会坐落在任何沼泽区域上。

Input Format

第 1 行包含整数 NNMM

接下来的 NN 行每行包含 MM 个字符,形成一个描述地点的网格。字符 '.' 表示普通草地,而 'X' 表示沼泽区域。

Output Format

一个整数,表示 Bessie 可以用堡垒覆盖的最大面积。

5 6
......
..X..X
X..X..
......
..X...
16

Hint

在示例中,最优框架的位置由下面的 f 表示:

.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...