一般解空间的优先队列式分支限界法

Description:

                                                                                

试设计一个用优先队列式分支限界法搜索一般解空间的函数。该函数的参数包括结点可

行性判定函数和上界函数等必要的函数，并将此函数用于解布线问题。

印刷电路板将布线区域划分成n×m个方格阵列如图(a)所示。精确的电路布线问题要求确定连接方格a的中点到方格b 的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图(b)所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允许

穿过被封锁的方格.

 

对于给定的布线区域，编程计算最短布线方案。

Input:

 

第一行有3 个正整数n，m，k，分别表示布线区域方格阵列的行数，列数和封闭的方格数。接下来的k行中，每行2 个正整数，表示被封闭的方格所在的行号和列号。最后的2 行，每行也有2 个正整数，分别表示开始布线的方格(p，q)和结束布线的方格(r，s)。

Output:

 

将计算出的最短布线长度和最短布线方案输出。第一行是最短布线长度。从第2 行起，每行2 个正整数，表示布线经过的方格坐标。如果无法布线则输出“No Solution!”。

Sample Input:

8 8 3
3 3
4 5
6 6
2 1
7 7

Sample Output:

11
2 1
3 1
4 1
5 1
6 1
7 1
7 2
7 3
7 4
7 5
7 6
7 7

Note:

 

本题由旧版NOJ导入，来源： 算法设计与实验题解