OI题库

【题目描述】

有一个被划分成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