1523. [UVa 1214] 连线

【题目描述】

有一个被划分成$n\times 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