Cow Beauty Pageant

Hearing that the latest fashion trend was cows with three spots on their hides, Farmer John bought an entire herd of three-spot cows. Unfortunately, fashion changes quickly, and the hottest look now is a cow with only one spot!

Farmer John wants to make his herd more fashionable by painting each cow so that its three spots merge into one. A cow's hide is given as an $N \times M$ grid of characters like this:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

Here each 'X' is part of a spot. Two 'X's belong to the same spot if they are vertically or horizontally adjacent (diagonal adjacency does not count), so the figure above has exactly three spots. Every cow in the herd has exactly three spots.

Farmer John wants to use as little paint as possible to merge the three spots into one. In the example above he can do it by painting only four extra cells with 'X' (the new cells are marked with '*' below to make them easier to see):

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....

Please determine the minimum number of new 'X's that must be painted to merge the three spots into one single spot.

• Line 1: Two space-separated integers $N$ and $M$ ($1 \le N, M \le 50$).
• Lines 2 through $N+1$: Each contains a length-$M$ string of 'X' and '.' describing one row of the cow-hide pattern.

• Line 1: The minimum number of new 'X's that must be added to the pattern to obtain one single spot.

The example pattern has three separate spots, and painting four new 'X' cells is enough to join the three spots into one.