JOIN
Get Time

   Problem Statement  

 Problem Statement for FoxBomb

Problem Statement

    Fox Ciel is playing a game named Bomberfox. The game is played on a rectangular grid divided into 1x1 cells. Each cell is either a wall or a floor. Initially, all the floor is colored white.

Ciel can place bombs onto floor cells of the field. When a bomb explodes, its blast spreads to four direction - up, down, left and right. In each of the four directions the blast only stops when it hits the wall. When a cell gets hit by a blast, its color turns to red. The purpose of the game is to color all floor cells red by placing as few bombs as possible.

You are given a String[] grid, which represents the grid of the game. The j-th character of the i-th element of grid is '#' if the cell in the j-th column of the i-th row is a wall, and is '.' if the cell is a floor (quotes for clarity). Your method must return the minimum required number of bombs.

In this problem, there is an additional constraint: the floor cells form a tree. A more formal specification follows: We say that two cells are adjacent when they share an edge. A path from cell A to cell B is a sequence of distinct cells such that the first cell in the sequence is cell A, the last cell is B, and each pair of consecutive cells in the sequence is adjacent. A floor-only path is a path such that all cells in it, including A and B, are floor cells. The test data for this task has the following property: For each pair of floor cells in the grid, there is exactly one floor-only path from one of them to the other.
 

Definition

    
Class:FoxBomb
Method:getMinimumCost
Parameters:String[]
Returns:int
Method signature:int getMinimumCost(String[] grid)
(be sure your method is public)
    
 

Constraints

-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will contain between 1 and 50 characters, inclusive.
-All elements of grid will contain the same number of characters.
-Each character of grid will be either '#' or '.'.
-grid will contain at least one '.' character.
-Floor cells of grid will form a tree. See the statement for formal constraints.
 

Examples

0)
    
{"#..."
,"..##"
,"#.##"}
Returns: 2
In this case, there are multiple optimal solutions. One of the optimal solution is shown below. Here, 'B' represents a cell to which Ciel should place a bomb.
#.B.
.B##
#.##
1)
    
{".#.#.#."
,"......."
,".#.#.#."}
Returns: 4
One optimal solution is shown below.
.#.#.#.
B.B.B.B
.#.#.#.
2)
    
{"######################################"
,"######################################"
,"###.....................##############"
,"###.###################.###....#...###"
,"###.###################.###.######.###"
,"###.###################.###.######.###"
,"###.###################.###.######.###"
,"###.###################.###.######.###"
,"###.###################.###.######.###"
,"###.........####........###.######.###"
,"###########.###########.###........###"
,"###########.###########.##########.###"
,"###########.###########.##########.###"
,"###########.###########.##########.###"
,"###########.###########.##########.###"
,"##..........##..........##########.###"
,"#######################............###"
,"######################################"}
Returns: 9
3)
    
{".#."
,"..."
,"#.#"
,"..."
,".#."}
Returns: 5
4)
    
{"."}
Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 539 Round 1 - Division I, Level Three