1948. [Ceoi2006]Connect
#1948. [Ceoi2006]Connect
题目描述
给定一个R*C大小的迷宫，其中R,C均为奇数 迷宫中坐标为两个奇数的点不能通过，称为障碍，迷宫中其他不能通过的点统称为墙壁 坐标为两个偶数的点可以通过，称为房间，迷宫中其他可通过的点称为走廊。迷宫有边界 迷宫中放置有若干个物品(偶数个)，物品一定放置在房间中 问如何将这些物品配对可以使得所有物品对之间路径的总和最小，任两条路径不能相交，并求路径
输入格式
第一行输入为两个整数： R与C(5 ≤ R ≤ 25，5 ≤ C ≤ 80) 其中R为行数，C为列数，R，C均为奇数。 接下来的R行每行包括C个字符，每个字符都是’+’、’|’、’-‘、空格或’X’中的一个，分别表示障碍及两种墙壁、空格表示房间或可通过的走廊，X表示房间中的物品。
输出格式
输出的第一行是一个整数，即最小分值。