Preparing NOJ

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

1000ms 65536K

Description:

                                                                                

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

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

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

穿过被封锁的方格.

 

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

Input:

 

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

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导入,来源: 算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1330

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet