P3086 [USACO13OPEN] Figure Eight G
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
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.
Explanation/Hint
For example, given this piece of marble:
```cpp
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
```
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 $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