8402: Figure Eight

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

农民约翰的奶牛最近收到了一大块大理石,不幸的是,它有许多缺陷.。为了描述这些,我们可以用n个正方形网格来表示一块大理石(5 < n = n = 300),其中字符“*”表示一个不完美和“。

母牛想雕刻一个号码“8”在这一块大理石(牛很喜欢数字“8”,因为他们对他们的每一个四英尺,有偶蹄有效地数到8,用“脚”)。然而,奶牛需要你的帮助,以确定最佳放置在图八块大理石。这里有一些属性定义一个有效的数字八:

图八包括两个矩形,一个顶部和一个底部。顶部和底部至少有一个单元在其内部。顶部矩形的底部边缘是底部矩形顶部边缘的一个(不一定是适当的)子集.。

图八只能刻在大理石的无瑕疵区域。

图八的美学得分等于其两个矩形所包围的区域的乘积.。奶牛希望最大限度地提高这一成绩。

输入格式

第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.

输入样例 复制

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

输出样例 复制

3888 

数据范围与提示

顶部的矩形面积6X9 = 54,和底部矩形面积12x6 = 72。因此,它的审美评分54x72 = 3888。

给出一个n×n的区域,其中有一些位置有瑕疵。现在要在没有瑕疵的位置中雕一个8”出来。

“8”字的定义为两个矩形框,框内面积均大于0,且一个矩形框的底边是是另一个矩形框的顶边的子集。

最大化两矩形框内面积的积。


分类标签