#P3135. [USACO16JAN] Fort Moo P

    ID: 2179 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>动态规划,dp2016USACO枚举构造

[USACO16JAN] Fort Moo P

题目描述

Bessie is building a fort with her friend Elsie. Like any good fort, this one needs to start with a sturdy frame. Bessie wants to build a frame in the shape of a one-meter-wide rectangular outline, atop which she will build the fort.

Bessie has already chosen a site on which to build the fort -- a piece of land measuring NN meters by MM meters (1N,M2001 \leq N, M \leq 200). Unfortunately, the site has some swampy areas that cannot be used to support the frame. Please help Bessie determine the largest area she can cover with her fort (the area of

the rectangle supported by the frame), such that the frame avoids sitting on any of the swampy areas.

奶牛 Bessie 和 Elsie 正在建她们的城堡。这个城堡有一个框架,框架为长方形。现在输入一个 n×mn \times m 的地图,标注 . 为平地,标注 X 为沼泽地。框架的任何一点都不能出现在沼泽地上,求最大框架面积。

输入格式

Line 1 contains integers NN and MM.

The next NN lines each contain MM characters, forming a grid describing the

site. A character of '.' represents normal grass, while 'X' represents a swampy

spot.

输出格式

A single integer representing the maximum area that Bessie can cover with her

fort.

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

提示

In the example, the placement of the optimal frame is indicated by 'f's below:

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