Description

Farmer John's cows recently received a large piece of marble which, unfortunately, has a number of imperfections. We can represent the piece of marble by an N by N square grid (where 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. However, they need your help to determine the optimally placed figure eight. A valid figure eight is defined by the following properties:

• A figure eight consists of two rectangles, a top one and a bottom one.
• Both the top and bottom rectangles 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 marble.

The aesthetic score of a figure eight is equal to the product of the areas enclosed by its two rectangles. The goal is to maximize this score.

Input Format

• Line 1: A single integer N, the side length of the marble.
• Lines 2..N+1: Each line describes a row of the marble and contains N characters, each either '*' (an imperfection) or '.' (a flawless section).

Output Format

• Line 1: The highest aesthetic score of any figure eight that does not use any imperfect squares of the marble. If no figure eight is attainable, output -1.

15 
............... 
............... 
...*******..... 
.*....*.......* 
.*......*....*. 
....*.......... 
...*...****.... 
............... 
..**.*..*..*... 
...*...**.*.... 
*..*...*....... 
............... 
.....*..*...... 
.........*..... 
............... 

3888 

Hint

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 $6 \times 9 = 54$, and the bottom rectangle has area $12 \times 6 = 72$. Thus, its aesthetic score is $54 \times 72 = 3888$.

Translated by ChatGPT 5