Description

早些年，当著名的十六位三字母操作系统最常用于 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 游戏的起始位置，以实现可能的最小得分来进行游戏。测试数据将保证一个解，尽管不一定是唯一的，总是存在的。

Input Format

第一行输入为两个整数：$R$ 和 $C$，其中 $R$ 为行数，$C$ 为列数，$R$，$C$ 均为奇数。

接下来的 $R$ 行每行包括 $C$ 个字符，每个字符都是 +、|、-、空格或 X 中的一个，分别表示障碍及两种墙壁，空格表示房间或可通过的走廊，X 表示房间中的物品。

Output Format

输出的第一行是一个整数，即最小分值。

本题不要求输出合法方案。

17 15
+-+-+-+-+-+-+-+
|             |
+ + + + + + + +
|X  |   |     |
+ + + + + + + +
|   |   |  X  |
+-+ + + + + + +
|       |     |
+ + + +-+-+-+-+
|            X|
+ + +-+-+-+-+ +
|             |
+ + + + + + + +
|  X|         |
+ + + + + + + +
|  |          |
+-+-+-+-+-+-+-+

30

Hint

$5 \leqslant R \leqslant 25$，$5 \leqslant C \leqslant 80$。

题面翻译由 ChatGPT-4o 提供。