Connect

Long ago, when a sixteen-bit, three-letter operating system that ran on an 80x25 text terminal ruled the PC market, "Nibbles" was everyone's favourite computer game. This problem is not about Nibbles, however - it is about a game called "Connect", which is almost, but not quite, entirely unlike Nibbles.

Connect is played on a board of squares arranged in R rows and C columns, where both R and C are odd. Rows are numbered 1 to R and columns 1 to C. Every square is either free or blocked by a wall. In addition, every board obeys these rules:

• A square whose two coordinates are both even is a room. Rooms are never blocked.
• A square whose two coordinates are both odd is a barrier. Barriers are always blocked.
• Every other square is a corridor. A corridor may or may not be blocked.
• Corridors on the outer edge of the board are always blocked.

Barriers are drawn with the + character, blocked horizontal corridors with the | character, and blocked vertical corridors with the - character. Rooms and free corridors are drawn with the blank character.

At the start of the game an even number of figures (drawn with the uppercase letter X) are placed on the board, each in its own room. A path between figures A and B is a sequence of free squares that starts at A, ends at B, and moves one step in one of the four cardinal directions at each stage (the path includes both endpoints A and B). The length of a path is the number of steps needed to walk from A to B, which equals the number of squares on the path minus one.

The player must first split all of the figures into pairs and then connect the two figures of every pair with a path, so that no two paths share a square. The score of a finished game is the sum of the lengths of all the paths.

+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+
|             |            |  .......    | 
+ + + + + + + +            + +.+ + +.+ + + 
|X  |   |     |            |X..|   |.    | 
+ + + + + + + +            + + + + +.+ + + 
|   |   |  X  |            |   |   |..X  | 
+-+ + + + + + +            +-+ + + + + + + 
|       |     |            |       |     |
+ + + +-+-+-+-+            + + + +-+-+-+-+ 
|            X|            |            X|
+ + +-+-+-+-+ +            + + +-+-+-+-+.+ 
|             |            |  ...........| 
+ + + + + + + +            + +.+ + + + + + 
|  X|         |            | X|          | 
+ + + + + + + +            + + + + + + + + 
|   |         |            |   |         |
+-+-+-+-+-+-+-+            +-+-+-+-+-+-+-+

Given a starting position, determine the smallest score that can be achieved by pairing up every figure and joining each pair with paths that share no square. The test data guarantee that at least one valid way to connect all the figures always exists.

The first line contains two odd integers R and C (5 <= R <= 25, 5 <= C < 80) - the number of rows and columns.

Each of the next R lines contains C characters describing one row of the board. Each character is one of +, |, or - (a barrier or a blocked corridor), the blank character (a free corridor or a room), or X (a figure standing in a room).

There are at least two figures on the board, and their number is always even.

Print a single integer: the smallest possible score, that is, the minimum total path length over all ways of splitting every figure into pairs and connecting each pair with paths that share no square.