农民约翰的奶牛最近收到了一大块大理石,不幸的是,它有许多缺陷.。为了描述这些,我们可以用n个正方形网格来表示一块大理石(5 < n = n = 300),其中字符“*”表示一个不完美和“。
母牛想雕刻一个号码“8”在这一块大理石(牛很喜欢数字“8”,因为他们对他们的每一个四英尺,有偶蹄有效地数到8,用“脚”)。然而,奶牛需要你的帮助,以确定最佳放置在图八块大理石。这里有一些属性定义一个有效的数字八:
图八包括两个矩形,一个顶部和一个底部。顶部和底部至少有一个单元在其内部。顶部矩形的底部边缘是底部矩形顶部边缘的一个(不一定是适当的)子集.。
图八只能刻在大理石的无瑕疵区域。
图八的美学得分等于其两个矩形所包围的区域的乘积.。奶牛希望最大限度地提高这一成绩。
第1行:一个整数n,表示大理石的边长。
行2 N + 1:每行描述了一排大理石,并包含n个字符,每个都是“*”(缺陷)或'.' (完整)。
15
...............
...............
...*******.....
.*....*.......*
.*......*....*.
....*..........
...*...****....
...............
..**.*..*..*...
...*...**.*....
*..*...*.......
...............
.....*..*......
.........*.....
...............
3888
顶部的矩形面积6X9 = 54,和底部矩形面积12x6 = 72。因此,它的审美评分54x72 = 3888。
给出一个n×n的区域,其中有一些位置有瑕疵。现在要在没有瑕疵的位置中雕一个8”出来。
“8”字的定义为两个矩形框,框内面积均大于0,且一个矩形框的底边是是另一个矩形框的顶边的子集。
最大化两矩形框内面积的积。