USACO 2013 US Open, Gold
Problem 3. Figure Eight
Contest has ended.
Log in to allow submissions in analysis mode
Problem 3: Figure Eight [John Pardon, 2010]
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.
For example, given this piece of marble
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
the optimally placed eight is:
..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.
PROBLEM NAME: eight
INPUT FORMAT:
* 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).
SAMPLE INPUT (file eight.in):
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
OUTPUT FORMAT:
* 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.
SAMPLE OUTPUT (file eight.out):
3888
Contest has ended. No further submissions allowed.