Fort Moo

题目描述

贝茜正在和她的朋友艾尔茜一起建造一座堡垒。像任何合格的堡垒一样，它需要先从一个坚固的框架开始。贝茜想建造一个形状为宽度一米的矩形轮廓框架，在其上方搭建堡垒。

贝茜已经选定了建堡地点——一块大小为 $N$ 米乘 $M$ 米的土地（ $1 \leq N, M \leq 200$ ）。不幸的是，这块地上有一些沼泽区域，无法用来支撑框架。请帮助贝茜确定她的堡垒最多能覆盖多大的面积（由框架支撑的矩形面积），并且要求框架不能坐落在任何沼泽区域上。

第 1 行包含整数 $N$ 和 $M$ 。接下来的 $N$ 行每行包含 $M$ 个字符，构成一个描述地点的网格。字符 '.' 表示普通草地，字符 'X' 表示沼泽点。

输出一个整数，表示贝茜的堡垒最多能够覆盖的面积。

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

在示例中，最优框架的位置在下方用 'f' 标出： .ffff. .fX.fX Xf.Xf. .ffff. ..X... Problem credits: Nathan Pinsker

标签: USACO|2016|Platinum

USACO|2016|Platinum