连线

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file manhattanwiring.in Output file manhattanwiring.out

【题目描述】


有一个被划分成n*m网格的矩形区域。有两个格子被标上“2”,另外两个格子被标上“3”。一些格子被标记成障碍。你应当将两个“2”和两个“3”用不相交的线连接。这些线必须垂直或水平地连接方格的中心,并且不能越过障碍。

不能在障碍格中连线。一个格子中只能有至多一条线。因此,一条线不能与另一条线相交,也不能和它自己相交。在这些限制下,两条线的总长应当最小。规定方格的边长为1。特别地,连接某个格子相邻两边的线长度为1,而连接某个格子中心和它的某条边的线长度为1/2.


【输入格式】

输入包含至多150组数据。每组数据的格式如下所示:

第1行是两个正整数n,m(1<=n,m<=9)。

接下来n行每行有m个正整数,描述该格子。0表示空格,1表示障碍,2表示写有2的格子,3表示写有3的格子。

输入结束标志为n=m=0.

【输出格式】

对每组数据,输出两条折线的最小总长度。如果无解,输出0.

【样例输入】


5 5

0 0 0 0 0

0 0 0 3 0

2 0 2 0 0

1 0 1 1 1

0 0 0 0 3

2 3

2 2 0

0 3 3

6 5

2 0 0 0 0

0 3 0 0 0

0 0 0 0 0

1 1 1 0 0

0 0 0 0 0

0 0 2 3 0

5 9

0 0 0 0 0 0 0 0 0

0 0 0 0 3 0 0 0 0

0 2 0 0 0 0 0 2 0

0 0 0 0 3 0 0 0 0

0 0 0 0 0 0 0 0 0

9 9

3 0 0 0 0 0 0 0 2

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

2 0 0 0 0 0 0 0 3

9 9

0 0 0 1 0 0 0 0 0

0 2 0 1 0 0 0 0 3

0 0 0 1 0 0 0 0 2

0 0 0 1 0 0 0 0 3

0 0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

9 9

0 0 0 0 0 0 0 0 0

0 3 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 2 3 2

0 0


【样例输出】


18

2

17

12

0

52

43


【提示】

UVa上的图挂了,大家去《算法竞赛入门经典训练指南》P386看题吧……

【来源】

UVa1214 Manhattan Wiring

刘汝佳,《算法竞赛入门经典训练指南》表6-4