同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21241_SparetheEwoks!

2022-5-16 18:19| 发布者: Hocassian| 查看: 45| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-8950552151800-Problem List-采集的数据-后羿采集器.html

Pro.ID

21241

Title

Spare the Ewoks!

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21241

AC

Submit

Ratio

时间&空间限制

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

Rejuvenated after the successful siege of Cloud City, Emperor Palpatine has commissioned you to begin construction of a new Imperial base on the forest moon of Endor. Endor, however, is home to a species of cuddly creatures known as the `Ewoks.'

Having a soft spot in his otherwise callous heart for these Ewoks, Palpatine has ordered that none of the existing Ewok homes must be disturbed. Furthermore, he has asked that you make the base as large as possible in terms of total area, and that this area may be divided among up to three rectangular buildings. Help Palpatine in his quest for intergalactic domination!

For this problem, you are provided a map of Endor in the form of an m x n rectangular grid, where some of the cells have been marked as Ewok homes, and other cells are empty. Your goal is to place up to three (but possibly fewer) rectangular buildings on this grid in such a way that no two buildings overlap with each other, and no building is placed over an Ewok home.

输入

The input will contain multiple test cases. Each test case begins with a single line containing a pair of integers m and n (where 1 <= m <= 250 and 1 <= n <= 250) representing the number of rows and columns in the grid. The next m lines then specify the map of Endor; specifically, each line will contain n characters, where each character is either '.' (a period) standing for an empty space, or 'e' (lower case E) for an Ewok home. After the final test case will be a single line containing "0 0"; this line should not be processed.

输出

Description

Input

Output

For each input test case, print a single integer indicating the maximum area that can be covered by buildings.

Sample Input

1 2
..
5 6
eee...
ee...e
ee...e
e...ee
e..eee
8 12
eee...eee...
eee...eee...
ee...eee..ee
eee...eee...
ee...eee...e
eee..eee..ee
ee..eee..eee
eee..eee...e
0 0

Sample Output

2
13
22

Source

Pacific NW 2009

样例输入

1 2
..
5 6
eee...
ee...e
ee...e
e...ee
e..eee
8 12
eee...eee...
eee...eee...
ee...eee..ee
eee...eee...
ee...eee...e
eee..eee..ee
ee..eee..eee
eee..eee...e
0 0