分支限界法之布线问题

　　一、要求：

　　1、输入电路板区域n*m以及布线的起始位置和结束位置；

　　2、输出布线方案；

　　3、可以使用c或者vc实现

　　二、问题分析及实验原理：

　　在n*m的方格阵列中存在封锁区域（布线时必须绕开的区域），找到起始位置到目标位置的最短路径。从目标位置开始向起始位置回溯，逐步构造最优解。每次向标记距离比当前方格标记距离少1的相邻方格移动，直到到达起始方格为止。

　　三、算法程序源代码：

　　#include

　　#include

　　using namespace std;

　　typedef struct

　　{

　　int row ;

　　int col ;

　　}Position;

　　typedef struct

　　{

　　//struct Position;

　　int row[10000] ;

　　int col[10000] ;

　　int end;

　　int begin ;

　　}Queue;

　　int grid[100][100];

　　Position start, finish;

　　int PathLen = 0;

　　Position * path;

　　int n , m , a , b , x ;

　　bool FindPath(Position start,Position finish)

　　{//计算从起点位置start到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false

　　if((start.row==finish.row) && (start.col==finish.col))

　　{

　　PathLen=0;

　　return true;

　　} //start=finish

　　//设置方格阵列“围墙”