FoxBomb

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.