F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

海岸线

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 479    Accepted Submission(s): 258


Problem Description
欢迎来到珠海!

由于土地资源越来越紧张,使得许多海滨城市都只能依靠填海来扩展市区以求发展。作为Z市的决策人,在仔细观察了Z市地图之后,你准备通过填充某些海域来扩展Z市的海岸线到最长,来吸引更多的游客前来旅游度假。为了简化问题,假设地图为一个N*M的格子,其中一些是陆地,一些是可以填充的浅海域,一些是不可填充的深海域。这里定义海岸线的长度为一个联通块陆地(可能包含浅海域填充变为的陆地)的边缘长度,两个格子至少有一个公共边,则视为联通。

值得注意的是,这里Z市的陆地区域可以是不联通的,并且整个地图都处在海洋之中,也就是说,Z市是由一些孤岛组成的,比如像,夏威夷?

你的任务是,填充某些浅海域,使得所有岛屿的海岸线之和最长。
 

Input
输入第一行为T,表示有T组测试数据。
每组数据以两个整数N和M开始,表示地图的规模。接下来的N行,每一行包含一个长度为M的字符串,表示地图,‘.’表示陆地,’E’表示浅海域,’D’表示深海域。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N, M <= 47
 

Output
对每组数据,先输出为第几组数据,然后输出最长的海岸线长度。
 

Sample Input
3 2 2 EE EE 3 3 EEE .E. EEE 3 3 EEE DED EEE
 

Sample Output
Case 1: 8 Case 2: 16 Case 3: 20
 

Hint

对于第三组样例,一种可行方案是:

.E.
D.D
.E.

这样5个孤立小岛的海岸线总长为4 * 5 = 20。
 

Author
Isea@WHU
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 20:21:57, Gzip enabled