Manhattan Wiring

题意翻译

题目大意 n×m网格里有空格和障碍,还有两个2和两个3.要求把这两个2和两个3各用一条折线连起来,使得总长度尽量小(线必须穿过格子中心,每个单位正方形的边长为1)。 限制条件如下:障碍格里不能有线,而每个空格里最多只能有一条线。由此可知,两条折线不能相交,每条折线不能自交。 如图所示,折线总长度为18(2、2、3、3格子中各有一条长度0.5的线)。 输入格式 输入包含多组数据。每组数据的第一行为正整数n、m(1≤n,m≤9),以下n行每行为m个整数,描述该网格。0表示空格,1表示障碍,2表示写有“2”的格子,3表示写有“3”的格子。 输出格式 对于每组数据输出一行,输出两条折线最小总长度,如果无解,输出0。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3655 [PDF](https://uva.onlinejudge.org/external/12/p1214.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点