Connect: Minimize Total Disjoint Path Length

The game Connect is played on a board of R rows and \(C\) columns (both odd), where each cell is either free or blocked. The board obeys the following rules:

• Cells with both coordinates even (rooms) are never blocked.
• Cells with both coordinates odd (barriers) are always blocked and are represented by the character +.
• Other cells are corridors which may be free (a blank space) or blocked. Blocked horizontal corridors are represented by | and blocked vertical corridors by -. Also, corridors along the edge of the board are always blocked.

At the start an even number of figures (denoted by X) are placed – each in a different room. A path between two figures is a sequence of free squares (moving one step up, down, left or right at each move) that starts at one figure and ends at the other; its length is the number of steps (which is one less than the number of cells in the path).

The goal is to pair up all figures and, for each pair, find a simple (non–self–intersecting) path connecting them such that no two paths share any cell. The final score is defined as the sum of the lengths of the connecting paths. Your task is to write a program that, given the initial board configuration, finds a set of disjoint connecting paths that yields the minimum total score. It is guaranteed that a solution exists.

Note: All formulas are rendered in \(\LaTeX\) (for example, the board has \(R\) rows and \(C\) columns, and rooms are at positions \((2i,2j)\)).

inputFormat

The input begins with a line containing two odd integers \(R\) and \(C\) (the number of rows and columns). Following this are \(R\) lines, each containing exactly \(C\) characters, representing the board. The characters are as follows:

• +: Barriers (always blocked).
• |: Blocked horizontal corridors.
• -: Blocked vertical corridors.
• (a blank space): Either a free corridor or a room.
• X: A room with a figure. (Rooms appear only at positions with both coordinates even.)

You may assume that there is an even number of X characters and that a solution exists.

outputFormat

Output a single integer – the minimum possible total score (i.e. the sum of the lengths of the disjoint paths connecting the paired figures) that can be achieved.

sample

5 5
+|+|+
-X X-
+ + +
-X X-
+|+|+

4