Islands#78
To keep up with modern trends, the government of Olympia plans to build several artificial islands to attract tourists. The map of these islands is given as an N \times M grid. Each cell of the grid is either land or water. A group of land cells forms an island if it is possible to travel between any two cells in the group by moving only through horizontally or vertically adjacent land cells, and there are no other land cells outside this group that are connected in this way.
For convenience, it has been decided to connect some of the islands with bridges so that all islands become interconnected. A bridge can only be built along a straight horizontal or vertical line, must start and end at land cells, and may only pass through water cells in between. The cost of constructing a bridge is equal to the number of water cells it passes through. Your task is to determine the minimum possible total cost for building a set of bridges so that all islands are connected (i.e., you can travel between any two land cells by moving through adjacent land cells or using bridges). Different bridges are allowed to cross the same water cell at different elevations.
The first line contains two integers and (1 \leq N, M \leq 500), the dimensions of the island map. The next lines each contain characters: either (water) or (land).
Print a single integer — the minimal total cost to build the bridges. If it is impossible to connect all islands with bridges, print -1.
Example 1