P3086 [USACO13OPEN] Figure Eight G
题目描述
Farmer John 的奶牛最近收到了一大块大理石，但这块大理石有一些瑕疵。为了描述这些瑕疵，我们可以将这块大理石表示为一个 $N \times N$ 的正方形网格 ($5 \le N \le 300$)。其中字符 `*` 代表一个瑕疵，`.` 代表大理石的一个完美部分。
奶牛们想在这块大理石上刻一个数字 “8”。然而，奶牛需要你的帮助来确定在这块大理石上放置得最优的“8”。以下是一些定义有效“8”的属性：
- 一个“8”由两个矩形组成：一个上矩形和一个下矩形。
- 上矩形和下矩形的内部都至少包含一个单元格（这意味着每个矩形的宽度和高度都至少为 $3$）。
- 上矩形的底边是下矩形顶边的一个（不一定是真）子集。（这意味着两个矩形共用一行，且上矩形的宽度小于等于下矩形的宽度，并且在水平方向上完全位于下矩形的范围内）。
- 这个“8”只能从大理石的完美区域（即字符为 `.` 的区域）刻出。（这意味着构成这两个矩形**边框**的所有单元格必须原本是 `.`，矩形内部可以包含瑕疵 `*`）。
一个“8”的美学分数等于其两个矩形所围成区域的面积的乘积。奶牛希望最大化这个分数。
例如，给定这块大理石：
```text
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
```
最优放置的“8”如下：
```text
..88888888888..
..8.........8..
..8*******..8..
.*8...*.....8.*
.*8.....*...8*.
..8.*.......8..
..8*...****.8..
.88888888888888
.8**.*..*..*..8
.8.*...**.*...8
*8.*...*......8
.8............8
.8...*..*.....8
.8.......*....8
.88888888888888
```
上矩形的面积为 $6 \times 9 = 54$，下矩形的面积为 $12 \times 6 = 72$。因此，它的美学分数为 $54 \times 72 = 3888$。
输入格式
第 $1$ 行：一个整数 $N$，表示大理石的边长。
第 $2$ 到 $N+1$ 行：每行描述大理石的一行，包含 $N$ 个字符，每个字符是 `*`（瑕疵）或 `.`（完美部分）。
输出格式
输出一行一个整数，表示任何不占用大理石瑕疵方格（即边框完全由 `.` 组成）的有效“8”的最高美学分数。如果无法刻出“8”，则输出 `-1`。