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 jth character of the ith element of grid is '#' if the cell in the jth column of the ith 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 flooronly 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 flooronly 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)    
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.
