P6131 [USACO11NOV] Cow Beauty Pageant S

It is said that cows with three spots on their skin have recently become popular, so Farmer John quickly bought many such cows. But trends change, and now cows with only one spot are popular. FJ decides to paint his cows so that the three spots merge into one. The cow’s skin is represented by an $N \times M$ grid, like this: ```plain ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX.... ``` Each `X` represents part of a spot. If two `X` cells are adjacent vertically or horizontally, then they belong to the same spot (diagonal adjacency does not count). Therefore, the grid above represents a cow with three spots. FJ can change the pattern by painting some `.` cells into `X`. He wants to use as little paint as possible to merge the three spots into a single spot. For the grid above, the following is one optimal way (only 4 cells are painted; newly painted cells are marked with `*`): ```plain ................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX.... ``` Now, please help FJ compute the minimum number of cells that need to be painted to merge the three spots into one.

The first line contains two integers $N, M$ ($1 \leq N, M \leq 50$). The next $N$ lines each contain $M$ characters (`.` or `X`), describing the distribution of spots on the cow’s skin. It is guaranteed that the cow has exactly three spots.

Output the minimum number of cells that need to be painted to merge the three spots into one.

Translated by ChatGPT 5