一、要求:
1、输入电路板区域n*m以及布线的起始位置和结束位置;
2、输出布线方案;
3、可以使用c或者vc实现
二、问题分析及实验原理:
在n*m的方格阵列中存在封锁区域(布线时必须绕开的区域),找到起始位置到目标位置的最短路径。从目标位置开始向起始位置回溯,逐步构造最优解。每次向标记距离比当前方格标记距离少1的相邻方格移动,直到到达起始方格为止。
三、算法程序源代码:
#include <iostream>
#include<stdio.h>
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
//设置方格阵列“围墙”
int i ;
for( i=0; i<= m+1; i++)
grid[0][i]=grid[n+1][i]=1; //顶部和底部
for( i=0; i<= n+1; i++)
grid[i][0]=grid[i][m+1]=1; //左翼和右翼
int j ;
//初始化相对位移
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;
Queue Q ;
Q.end = 0 ;
Q.begin = 0 ;
do {//标记相邻可达方格
for( 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)
{
责任编辑:小草