电路布线问题

【问题描述】

印刷电路板将布线区域划分为n╳n个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为a，终止位置为b，求解电路布线问题。

【设计要求】

设计印刷电路板的布线模拟程序。

（1）采用栈或队列等数据结构。

（2）采用穷举法的回溯搜索，求a到b可能的布线线路。

（3）推荐采用层次优先搜索，求a到b最优的布线线路。

-Circuit wiring problem [Problem Descr iption] printed circuit board wiring area will be divided into n 鈺?n squares array. In wiring, circuit wiring only along a straight line or right angle. To avoid the lines intersect, the boxes have to do the wiring block tag. Let the starting position is a, the end position is b, solve the problem of the circuit wiring. [Design] design printed circuit board layout simulation program. (1) using data structures such as stacks or queues. (2) using the brute-force method of backtracking search, find a to b possible wiring lines. (3) recommended levels-first search, find a to b optimal wiring lines.