TopCoder problem "DiamondGame" used in Round 1 (Division I Level Two)



Problem Statement

    

The diamond game is played on a rectangular board, each cell of which is either empty or occupied by a diamond. First, you remove one arbitrary diamond from the board. Then, you continuously remove diamonds from cells that are vertically or horizontally adjacent to at least one cell from which you have previously (any time before) removed a diamond . Do this until you can no longer remove any more diamonds. Your goal is to remove as many diamonds as possible. At the beginning of the game, you have an extra diamond in your hand. You can optionally place it in any one of the empty cells before you start playing the game.

The game board is given as a String[] diamondsBoard, where each cell is marked with a '*' or '.'. A '*' represents a cell occupied by a diamond and a '.' represents an empty cell. You are to return the maximum number of diamonds you can remove not including the extra diamond.

 

Definition

    
Class:DiamondGame
Method:maximumDiamond
Parameters:String[]
Returns:int
Method signature:int maximumDiamond(String[] diamondsBoard)
(be sure your method is public)
    
 

Constraints

-diamondsBoard will contain between 1 and 50 elements, inclusive.
-Each element of diamondsBoard will contain between 1 and 50 characters, inclusive.
-Each element of diamondsBoard will contain the same number of characters.
-Each character in each element of diamondsBoard will be either '*' or '.'.
 

Examples

0)
    
{"*",
 "*",
 ".",
 "*"}
Returns: 3
1)
    
{"*.*",
 "..*"}
Returns: 3
If you place the extra diamond in the cell at 1-st row, 2-nd column, you can remove all diamonds from the board.
2)
    
{"...",
 "...",
 "...",
 "..."}
Returns: 0
3)
    
{"*..",
 "*.*"}
Returns: 3
4)
    
{"*",
 "*"}
Returns: 2
Here you don't have a place to put the extra diamond, so you don't use it.
5)
    
{"...***.**.****",
 ".*****.*..*.**",
 "**..***..****.",
 ".*****.*..*.*.",
 ".***.**.***.**",
 "**...****..*.*",
 "*****.*.******",
 "....****.**.*.",
 "**.*...****.**",
 "**.****.**.**."}
Returns: 83
6)
    
{"**..**..**.***",
 "**..***..*.*.*",
 "*.*******..**.",
 "*.*..*.*..***.",
 "***..*...**..*",
 ".*.***..*.**..",
 "*******.*****.",
 "***.*.*.***..*",
 ".**...*..****.",
 ".**.*..******.",
 "*.*.*****.*.**",
 "*.*.***..*.*.*",
 "..*****.*.**..",
 ".*.*.***.*****",
 "...**.**.****.",
 "...*****.*****",
 "..*****.**.*.*"}
Returns: 139

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8777

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12212&pm=8777

Writer:

stone

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Search