UVA1214 Manhattan Wiring

题目描述

题目大意 n×m网格里有空格和障碍,还有两个2和两个3.要求把这两个2和两个3各用一条折线连起来,使得总长度尽量小(线必须穿过格子中心,每个单位正方形的边长为1)。 限制条件如下:障碍格里不能有线,而每个空格里最多只能有一条线。由此可知,两条折线不能相交,每条折线不能自交。 如图所示,折线总长度为18(2、2、3、3格子中各有一条长度0.5的线)。

输入格式

输出格式