#1948. [Ceoi2006]Connect

内存限制:64 MiB 时间限制:5 Sec

题目描述

给定一个R*C大小的迷宫,其中R,C均为奇数 迷宫中坐标为两个奇数的点不能通过,称为障碍,迷宫中其他不能通过的点统称为墙壁 坐标为两个偶数的点可以通过,称为房间,迷宫中其他可通过的点称为走廊。迷宫有边界 迷宫中放置有若干个物品(偶数个),物品一定放置在房间中 问如何将这些物品配对可以使得所有物品对之间路径的总和最小,任两条路径不能相交,并求路径

输入格式

第一行输入为两个整数: R与C(5 ≤ R ≤ 25,5 ≤ C ≤ 80) 其中R为行数,C为列数,R,C均为奇数。 接下来的R行每行包括C个字符,每个字符都是’+’、’|’、’-‘、空格或’X’中的一个,分别表示障碍及两种墙壁、空格表示房间或可通过的走廊,X表示房间中的物品。

输出格式

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

样例

样例输入


			

样例输出


			

数据范围与提示