[USACO13OPEN] Figure Eight G
题目描述
Farmer John's cows recently received a large piece of marble, which, unfortunately, has a number of imperfections. To describe these, we can represent the piece of marble by an N by N square grid (5 <= N <= 300), where the character '\*' represents an imperfection and '.' represents a flawless section of the marble.
The cows want to carve a number "8" in this piece of marble (cows are quite fond of the number "8" since they have cloven hooves on each of their four feet, so they can effectively count up to 8 using their "toes"). However, the cows need your help to determine the optimally placed figure eight in the piece of marble. Here are a few properties that define a valid figure eight:
\* A figure eight consists of two rectangles, a top and a bottom. \* Both the top and bottom have at least one cell in their interior. \* The bottom edge of the top rectangle is a (not necessarily proper) subset of the top edge of the bottom rectangle.
\* The figure eight can only be carved from flawless regions of the piece of marble.
The aesthetic score of a figure eight is equal to the product of the areas enclosed by its two rectangles. The cows wish to maximize this score.
```cpp
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
```
For example, given this piece of marble
the optimally placed eight is:
```cpp
..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
```
The top rectangle has area 6x9=54, and the bottom rectangle has area 12x6=72. Thus, its aesthetic score is 54x72=3888.
农民约翰的奶牛最近收到了一大块大理石，不幸的是，它有许多缺陷.。为了描述这些，我们可以用n个正方形网格来表示一块大理石（5 < n = n = 300），其中字符“\*”表示一个不完美和“。
母牛想雕刻一个号码“8”在这一块大理石（牛很喜欢数字“8”，因为他们对他们的每一个四英尺，有偶蹄有效地数到8，用“脚”）。然而，奶牛需要你的帮助，以确定最佳放置在图八块大理石。这里有一些属性定义一个有效的数字八：
图八包括两个矩形，一个顶部和一个底部。顶部和底部至少有一个单元在其内部。顶部矩形的底部边缘是底部矩形顶部边缘的一个（不一定是适当的）子集.。
图八只能刻在大理石的无瑕疵区域。
图八的美学得分等于其两个矩形所包围的区域的乘积.。奶牛希望最大限度地提高这一成绩。
输入输出格式
输入格式
\* Line 1: A single integer N, indicating the side length of the marble.
\* Lines 2..N+1: Each line describes a row of the marble, and contains N characters which are each either '\*' (an imperfection) or '.' (a flawless section).
第1行：一个整数n，表示大理石的边长。
行2 N + 1：每行描述了一排大理石，并包含n个字符，每个都是“\*”（缺陷）或'.' (完整)。
输出格式
\* Line 1: The highest aesthetic score of any figure eight which doesn't use any imperfect squares of the marble. If no figure eight is attainable, then output -1.
输入输出样例
输入样例 #1
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
输出样例 #1
3888
说明
顶部的矩形面积6X9 = 54，和底部矩形面积12x6 = 72。因此，它的审美评分54x72 = 3888。
给出一个n×n的区域，其中有一些位置有瑕疵。现在要在没有瑕疵的位置中雕一个8”出来。
“8”字的定义为两个矩形框，框内面积均大于0，且一个矩形框的底边是是另一个矩形框的顶边的子集。
最大化两矩形框内面积的积。
感谢 @3505515693qq 提供翻译