Merging Spots on a Cow

Farmer John once had three spots on his cow, but the latest fashion is to have just one spot. The cow's hide is represented by an \(N \times M\) grid with characters X and .. Each X indicates part of a spot, and two X's are in the same spot if they are adjacent horizontally or vertically (diagonals do not count). FJ is allowed to paint additional cells (i.e. change . into X) in order to merge the three spots into one. Your task is to compute the minimum number of cells that must be painted in order to connect all three spots into a single connected component.

A cell painted with new paint will “bridge” two or more spots if it is placed strategically. Note that if two painted cells are adjacent (or a painted cell is adjacent to an original X cell) then they together form a continuous connection. Formally, if you have two cells at coordinates \( (x_1, y_1) \) and \( (x_2, y_2) \), then the cost to connect them directly is given by the Manhattan distance minus 1, i.e., \(\text{cost} = |x_1-x_2|+|y_1-y_2|-1\).

It is guaranteed that the grid contains exactly three spots. The solution may involve selecting one cell as a meeting point for the three spots (using multi‐source breadth-first search to compute distances) or by combining optimal pairwise connections between spots.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns). The next \(N\) lines each contain a string of length \(M\) composed only of characters X and ., representing the cow's hide.

Example:

6 18
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

outputFormat

Output a single integer, the minimum number of cells that must be painted to merge the three spots into one.

sample

6 18
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

4