P6889 [CEOI 2006] CONNECT

早些年，当著名的十六位三字母操作系统最常用于 25x80 终端并主导 PC 市场时，“Nibbles” 是每个人最喜欢的电脑游戏。然而，这个问题与 Nibbles 无关——它与一个名为“Connect”的游戏有关，这个游戏几乎完全不像 Nibbles。 Connect 在一个由方格组成的棋盘上进行，棋盘由 R 行和 C 列组成，其中 R 和 C 都是**奇数**。行和列分别编号为 1 到 R 和 1 到 C。棋盘上的每个位置要么是空闲的，要么被墙壁阻挡。此外，每个棋盘满足以下约束： - **两个坐标都是偶数**的方格称为房间。它们**永远不会被阻挡**。 - **两个坐标都是奇数**的方格称为障碍物。它们**总是被阻挡**。 - 所有其他方格称为走廊。它们可能被阻挡，也可能不被阻挡。 - **沿着棋盘边缘**的走廊**总是被阻挡**。 障碍物用 '+'（加号）字符表示，阻挡的水平走廊用 '|'（竖线）字符表示，而阻挡的垂直走廊用 '–'（减号）字符表示。房间和空闲走廊用空白字符表示。 在游戏开始时，**偶数个**棋子（用大写字母 'X' 表示）被放置在棋盘上——每个棋子在一个单独的**房间**里。棋子 A 和 B 之间的路径是一系列**空闲**方格，从 A 开始，以 B 结束，每一步都在**四个可能的方向**之一移动（路径包括两个端点方格，A 和 B）。路径的长度是从 A 到 B 所需的总步数（等于路径中包含的方格数减一）。 玩家的目标是首先**将所有棋子分成对**，然后，对于每对棋子，**用路径连接**这两个棋子。对应该以这样的方式连接，即**没有两条路径共享一个公共方格**。 对于完成的游戏，得分定义为所有路径的长度之和。 编写一个程序，给定 Connect 游戏的起始位置，以实现**可能的最小得分**来进行游戏。测试数据将保证一个解，尽管不一定是唯一的，总是存在的。

第一行输入为两个整数：$R$ 和 $C$，其中 $R$ 为行数，$C$ 为列数，$R$，$C$ 均为奇数。 接下来的 $R$ 行每行包括 $C$ 个字符，每个字符都是 `+`、`|`、`-`、空格或 `X` 中的一个，分别表示障碍及两种墙壁，空格表示房间或可通过的走廊，`X` 表示房间中的物品。

输出的第一行是一个整数，即最小分值。 本题**不要求**输出合法方案。

$5 \leqslant R \leqslant 25$，$5 \leqslant C \leqslant 80$。 题面翻译由 ChatGPT-4o 提供。