Figure Eight
플래티넘 I의견: 0
Farmer John's cows recently received a large piece of marble, which has a number of imperfections. We represent the piece of marble by an N by N square grid (5 <= N <= 300), where '*' represents an imperfection and '.' represents a flawless section.
The cows want to carve a number "8" in this piece of marble. A valid figure eight has these properties:
- 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.
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).
The highest aesthetic score of any figure eight which doesn't use any imperfect squares of the marble. If no figure eight is attainable, output -1.
eight.ineight.out15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............3888Output details: The top rectangle has area 6x9=54 and the bottom 12x6=72, giving score 54x72=3888.
평가 및 의견
Figure Eight
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Figure Eight