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