3931 - 公园选址
题目描述
A 市城市规划局计划在新区开发一个新公园。规划局对新区的地形进行了勘探，并绘制了详细的地图。
新区地图是一个 N \times M 的长方形，其中 . 表示该位置是平地，X 表示该位置是山坡。
现要求在地图中找到一个最大的长方形，作为公园选址的位置，且要求长方形的每条边都必须在平地而不是在山坡上。
比如，假设下图是新区的地图：
......
..X..X
X..X..
......
..X...
在该地图中，可以找到面积为 16 的最大长方形，且长方形每条边都在平原上的方案如下（Z表示长方形的边）：
.ZZZZ.
.ZX.ZX
XZ.XZ.
.ZZZZ.
..X...
输入
第 1 行输入 2 个整数 N, M，表示新区地图的大小。
接下来 N 行，每行有 M 个字符，含义如题所述。
输出
输出一个整数，代表公园的最大面积。
样例
输入
5 6 ...... ..X..X X..X.. ...... ..X...
输出
16
输入
6 6 ...... .X.... ....X. ..X... .X.... ....X.
输出
24
输入
10 12 ............ ..X......... X........... ...........X .....X...X.. ............ .......X.... ............ ....X....... ............
输出
100
说明
样例 1 解释
请参考题目描述。
数据范围
对于 10\% 的数据，满足 1 \le N \le 200，M=2。
对于另外 20\% 的数据，满足 1 \le N,M \le 50。
对于 100\% 的数据，满足 1 \le N,M \le 200。
标签
