buxian.txt

这是个电路板布线问题的c++解决方法

bool FindPath(Position start,Position finish,int& PathLen,Position * &path)
{//计算从起点位置start到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false
if((start.row==finish.row) && (start.col==finish.col)
{PathLen=0; return true;} //start=finish
//设置方格阵列“围墙”
for(int i=0; i<= m+1; i++)
grid[0][i]=grid[n+1][i]=1; //顶部和底部
for(int i=0; i<= n+1; i++)
grid[i][0]=grid[i][m+1]=1; //左翼和右翼
//初始化相对位移
Position offset[4];
offset[0].row=0; offset[0].col=1;//右
offset[1].row=1; offset[1].col=0;//下
offset[2].row=0; offset[2].col=-1;//左
offset[3].row=-1; offset[3].col=0;//上
int NumOfNbrs=4;//相邻方格数
Position here,nbr;
Here.row=start.row;
Here.col=start.col;
Grid[start.row][start.col]=2;
//标记可达方格位置
LinkedQueue<Position> Q;
Do {//标记相邻可达方格
For(int I=0; I<NumOfNbrs; I++){
Nbr.row=here.row + offset[I].row;
Nbr.col=here.col+offset[I].col;
If(grid[nbr.row][nbr.col]==0){
//该方格未被标记
9
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
if((nbr.row==finish.row) &&
(nbr.col==finish.col)) break; //完成布线
Q.Add(nbr);}
}
//是否到达目标位置finish？
If((nbr.row==finish.row)
(nbr.col==finish.col)) break;//完成布线
//活结点队列是否非空？
If(Q.IsEmpty()) return false;//无解
Q.Delete(here);//取下一个扩展结点
}while(true);
//构造最短布线路径
PathLen=grid[finish.row][finish.col]-2;
path=new Position[PathLen];
//从目标位置finish开始向起始位置回溯
here=finish;
for(int j=PathLen-1; j>=0; j--){
path[j]=here;
//找前驱位置
for(int i=0; i<NumOfNbrs; i++){
nbr.row=here.row+offset[i].row;
nbr.col=here.col+offset[i];
if(grid[nbr.row][nbr.col]==j+2) break;
}
here=nbr;//向前移动
}
return true;
}