声明：凡代码问题，欢迎在评论区沟通。承蒙指正，一起成长！
目录
内容：(布线问题)印刷电路板将布线区域分成n*m个方格阵列，精确的电路布线问题要求确定连接方格A的中点到方格B的中点的最短布线方案，在布线时，电路只能沿直线或直角布线，为了避免线路相交，已经布线的方格做了封锁标记,其它线路不允许穿过被封锁的方格。
要求：随机输入n.m的矩阵，其中0表示未被封锁,-1表示被封锁,再输入两个坐标,表示A、B两个点。要求输出结果矩阵。
1.申请动态二维数组grid存储方格，输入规模m、n，以及始末点a、b坐标；
2.队列式分支限界算法FindPath：用二维数组grid表示所给的方格阵列。初始时，grid[i][]=0,表示该方格允许布线，grid[i][]=-1表示该方格被封锁，不允许布线。为了便于处理方格边界的情况，算法在所给方格阵列四周设置一道“围墙”，即增设标记为“1”的附加方格。开始时，测试初始方格与目标方格是否相同。如果这两个方格相同，则不必计算，直接返回最短距离0,否则设置方格阵列的“围墙”，初始化位移矩阵offset,将起始位置的距离标记为2。数字0和1用于表示方格的开放或封锁状态，所以在表示距离时不用这两个数字，将距离的值都加2。实际距离应为标记距离减2。算法从起始位置start开始，标记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记距离为4、5、…的方格，直至到达目标方格finish或活结点队列为空时为止；
3.在算法FindPath中：定义一个表示电路板上方格位置的类Position,它的两个私有成员row和col分别表示方格所在的行和列。在电路板的任何一个方格处，布线可沿右、下、左、上4个方向进行，沿这4个方向的移动分别记为移动0、1、2、3。offset[i].row和offset[i].col(i=0,1,2,3)分别给出了沿这4个方向前进一步相对于当前方格的相对位移；
4.释放中间变量的内存，打印矩阵即数组grid的全部值，以及布线路径的坐标值。
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
struct Position
{
int row;
int col;
};
int m,n; //规模
int **grid; //存储矩阵
void printPath(Position s,Position e);
bool FindPath(Position start,Position finish,int &PathLen,Position *&path);
int main()
{
int PathLen=0;
Position start,finish,*path;
cout << "Please enter the values of n and m:";
cin >>m>>n;
grid=(int **)malloc(n*sizeof(int *));
for(int p=0; p<=n; p++)
grid[p]=(int *)malloc(m*sizeof(int));
cout<<"Please enter a coordinates of the start point:";
cin>>start.col>>start.row;
cout<<"Please enter a coordinates of the end point:";
cin>>finish.col>>finish.row;
FindPath(start,finish,PathLen,path);
cout<<endl<<"The path map:"<<endl;
printPath(start,finish);
cout<<"Path:"<<"start_a("<<start.col<<","<<start.row<<")";
for(int i=0; i<PathLen; i++)
cout<<"-->("<<path[i].col<<","<<path[i].row<<")";
cout <<"end_b"<<endl << endl << endl;
return 0;
}
void printPath(Position s,Position e)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if((j==s.col)&&(i==s.row))
cout <<"a\t";
else if((j==e.col)&&(i==e.row))
cout <<"b\t";
else
cout<<grid[i][j]<<"\t";
}cout<<endl;
}cout<<endl<<endl;
}
bool FindPath(Position start,Position finish,int &PathLen,Position *&path)
{
if((start.row==finish.row) && (start.col==finish.col))
{
PathLen=0;
cout<<"start=finish"<<endl;
return true;
} //start=finish
cout << "Please enter a n*m matrix, where '0' means \"not blocked\", and '-1' means \"blocked\":"<<endl;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
cin>>grid[i][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]=0;
queue<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)
{
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线
Q.push(nbr);
}
}
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break; //完成布线
if(Q.empty()) //活结点队列是否非空
return false; //无解
here = Q.front();
Q.pop(); //取下一个扩展结点
}while(true);
PathLen=grid[finish.row][finish.col]; //构造最短布线路径
path=new Position[PathLen];
here=finish; //从目标位置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].col;
if(grid[nbr.row][nbr.col]==j)
break;
}
here=nbr; }
}
/*
#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int m,n;
int **grid;
int indexcount=0;
struct Position
{
int row;
int col;
};
void showPath(Position s,Position e)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if((j==s.col)&&(i==s.row))
cout <<"a\t";
else if((j==e.col)&&(i==e.row))
cout <<"b\t";
else
cout<<grid[i][j]<<"\t";
}
cout<<endl;
}
cout<<endl<<endl;
}
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;
cout<<"start=finish"<<endl;
return true;
} //start=finish
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
grid[i][j]=0;
}
//添加阻挡点
grid[1][1]=-1;
grid[2][2]=-1;
grid[3][3]=-1;
grid[5][3]=-1;
grid[6][2]=-1;
grid[4][5]=-1;
//初始化相对位移
cout<<"完整图"<<endl;
showPath(start,finish);
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]=0;
//grid[finish.row][finish.col]=99; //标记可达方格位置
cout<<"布线前图"<<endl;
showPath(start,finish);
queue<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)
{
//该方格未被标记
//cout<<grid[nbr.row][nbr.col]<<endl;//显示路标值
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
//cout<<nbr.col<<" "<<nbr.row<<endl;//显示坐标
if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线
Q.push(nbr);
}
}
//是否到达目标位置finish？
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线
//活结点队列是否非空？
if(Q.empty()) return false;//无解
here = Q.front();
//cout<<here.col<<" "<<here.row<<endl;
Q.pop();//取下一个扩展结点
//indexcount++;
// cout<<"下一节点"<<indexcount<<endl;
}
while(true);
//构造最短布线路径
PathLen=grid[finish.row][finish.col];
cout<<"the sign of end:"<<PathLen<<endl;
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].col;
if(grid[nbr.row][nbr.col]==j)
{
// cout<<j<<endl;
break;
}
}
here=nbr;//向前移动
}
return true;
}
int main()
{
cout << "Please enter the value of m、n:";
cin >>m>>n;
grid=(int **)malloc(n*sizeof(int *));
for(int p=0; p<=n; p++)
grid[p]=(int *)malloc(m*sizeof(int));
Position start;
start.col=2;
start.row=3;
cout<<"布线起点"<<endl;
cout<<start.col<<" "<<start.row<<endl;
Position finish;
finish.col=4;
finish.row=2;
cout<<"布线结束点"<<endl;
cout<<finish.col<<" "<<finish.row<<endl;
int PathLen=0;
Position *path;
FindPath(start,finish,PathLen,path);
cout<<"布线后路径图"<<endl;
showPath(start,finish);
cout<<"路径:"<<"a("<<start.col<<","<<start.row<<")";
for(int i=0; i<PathLen; i++)
{
cout<<"-->("<<path[i].col<<","<<path[i].row<<")";
}
cout <<"b"<<endl <<endl<< "布线问题完毕!" << endl;
return 0;
}
*/
#include <iostream>
#include <queue>
using namespace std;
int n=6;
int m=5;
int grid[7][7];
int indexcount=0;
struct Position
{
int row;
int col;
};
void showPath()
{
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
cout<<grid[i][j]<<"\t";
cout<<endl;
}
cout<<"------------------"<<endl;
}
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;
cout<<"start=finish"<<endl;
return true;
} //start=finish
//初始化图，-1为未访问
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
grid[i][j]=0;
}
/*/设置方格阵列“围墙”
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; //左翼和右翼 */
//添加阻挡点
grid[2][3]=-1;
grid[3][3]=-1;
grid[1][4]=-1;
grid[1][1]=111;
grid[4][3]=999;
//初始化相对位移
cout<<"完整图"<<endl;
showPath();
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]=0;
//标记可达方格位置
cout<<"布线前图"<<endl;
showPath();
queue<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]==-1)
{
//该方格未被标记
//cout<<grid[nbr.row][nbr.col]<<endl;//显示路标值
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
//cout<<nbr.col<<" "<<nbr.row<<endl;//显示坐标
}
if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线
Q.push(nbr);
}
//是否到达目标位置finish？
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线
//活结点队列是否非空？
if(Q.empty()) return false;//无解
here = Q.front();
//cout<<here.col<<" "<<here.row<<endl;
Q.pop();//取下一个扩展结点
indexcount++;
// cout<<"下一节点"<<indexcount<<endl;
}while(true);
//构造最短布线路径
PathLen=grid[finish.row][finish.col];
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].col;
if(grid[nbr.row][nbr.col]==j)
{
// cout<<j<<endl;
break;
}
}
here=nbr;//向前移动
}
return PathLen;
}
int main()
{
Position start;
start.col=1;
start.row=1;
cout<<"布线起点"<<endl;
cout<<start.col<<" "<<start.row<<endl;
Position finish;
finish.row=3;
finish.col=4;
cout<<"布线结束点"<<endl;
cout<<finish.col<<" "<<finish.row<<endl;
int PathLen=0;
Position *path;
FindPath(start,finish,PathLen,path);
cout<<"布线后路径图"<<endl;
showPath();
cout<<"路径"<<endl<<"Start";
for(int i=0; i<PathLen; i++)
{
cout<<"-->("<<path[i].col<<","<<path[i].row<<")";
}
cout <<"(End)"<<endl <<endl<< "布线问题完毕!" << endl;
return 0;
}
/*
#include <iostream>
#include <queue>
#include <windows.h>
using namespace std;
int m,n;
int **grid;
int indexcount=0;
struct Position
{
int row;
int col;
};
void showPath()
{
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
cout<<grid[i][j]<<" ";
cout<<endl;
}
cout<<"------------------"<<endl;
}
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;
cout<<"start=finish"<<endl;
return true;
} //start=finish
//设置方格阵列“围墙”
//初始化图，-1为未访问
for(int i=1; i<9; i++)
{
for(int j=1; j<9; j++)
grid[i][j]=-1;
}
//添加阻挡点
grid[2][3]=-2;
for(int i=0; i<= m+1; i++)
grid[0][i]=grid[n+1][i]=-2; //顶部和底部
for(int i=0; i<= n+1; i++)
grid[i][0]=grid[i][m+1]=-2; //左翼和右翼
//初始化相对位移
cout<<"完整图"<<endl;
showPath();
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]=0;
//标记可达方格位置
cout<<"布线前图"<<endl;
showPath();
queue<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]==-1)
{
//该方格未被标记
//cout<<grid[nbr.row][nbr.col]<<endl;//显示路标值
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
//cout<<nbr.col<<" "<<nbr.row<<endl;//显示坐标
}
if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线
Q.push(nbr);
}
//是否到达目标位置finish？
if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线
//活结点队列是否非空？
if(Q.empty()) return false;//无解
here = Q.front();
//cout<<here.col<<" "<<here.row<<endl;
Q.pop();//取下一个扩展结点
indexcount++;
// cout<<"下一节点"<<indexcount<<endl;
}
while(true);
//构造最短布线路径
PathLen=grid[finish.row][finish.col];
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].col;
if(grid[nbr.row][nbr.col]==j)
{
// cout<<j<<endl;
break;
}
}
here=nbr;//向前移动
}
return PathLen;
}
int main()
{
Position start;
start.col=1;
start.row=1;
cout<<"输入m、n:";
cin>>m>>n;
grid =(int **)malloc(m*sizeof(int *));
for(int p=0; p<m; p++)
{
grid[p]=(int *)malloc(n*sizeof(int));
for(int q=0; q<n; q++)
grid[p][q] = p*n+q;
}
cout<<"布线起点"<<endl;
cout<<start.col<<" "<<start.row<<endl;
Position finish;
finish.row=3;
finish.col=4;
cout<<"布线结束点"<<endl;
cout<<finish.col<<" "<<finish.row<<endl;
int PathLen=0;
Position *path;
FindPath(start,finish,PathLen,path);
cout<<"布线后路径图"<<endl;
showPath();
cout<<"路径"<<endl;
for(int i=0; i<PathLen; i++)
{
cout<<path[i].col<<" "<<path[i].row<<endl;
}
cout << "布线问题完毕!" << endl;
system("pause");
return 0;
}
*/
