UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4506. [Usaco2016 Jan]Fort Moo

Statistics 下载数据

Description

Bessie正在和她的朋友Elsie建一座堡垒。像任何好的堡垒一样,这需要从一个坚固的框架开始。Bessie想要在一
个矩形上建造堡垒,并在矩形周围围上1x1的框架。Bessie已经选择了一个建造堡垒的地方 —— 一块长宽分别为
为NM的土地(1<= N,M<= 200)。不幸的是,该地区有一些沼泽,不能用于支持框架。 请帮助贝西确定她可以用于
建造堡垒的最大矩形区域,避免框架搭建在任何一块沼泽上。题目大意:有一个NM的矩形包含字符‘.’和‘X’,
找出最大的边缘不包含‘X’的子矩形并输出它的面积。

Input

第一行包含整数N和M。接下来的N行每行包含M个字符,形成网格描述区域,‘.’表示正常的草地,‘X’表示沼泽

Output

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

Sample Input

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

Sample Output

16
In the example, the placement of the optimal frame is indicated by 'f's below:
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...

Hint

Source

Platinum 鸣谢g1n0st提供译文