电路布线问题C++.doc

《电路布线问题C++.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includeusingnamespacestd;structPosition{introw;intcol;};structTEAM{intx;inty;TEAM*next;};Positionstart,end,path[100];TEAM*team_l=NULL;inta[100][100];intm,n,path_len;voidOutput(){inti,j;cout<<"-------------------布线区域图-------------------";for(i=0;i

2、j>m>>n;cout<<"请输入开始点坐标(x,y):";cin>>start.row>>start.col;cout<<"请输入结束点坐标(x,y):";cin>>end.row>>end.col;cout<<"区域内是否有被占用点?(y/n

3、)";cin>>yes;while(yes=='y'){cout<<"请输入占用点的坐标(x,y):";cin>>x>>y;if(x<0

4、

5、x>m+1

6、

7、y<0

8、

9、y>n+1

10、

11、(x==start.row&&y==start.col)

12、

13、(x==end.row&&y==end.col)){cout<<"输入错误,请重新输入!!!";continue;}else{a[x][y]=-1;}cout<<"是否还有被占用点?(y/n)";cin>>yes;}for(x=0;x

14、[0]=-1;a[x][n+1]=-1;}return;}voidInq(Positionp){TEAM*t,*q;q=team_l;t=newTEAM;t->x=p.row;t->y=p.col;t->next=NULL;if(team_l==NULL){team_l=t;return;}while(q->next!=NULL){q=q->next;}q->next=t;return;}Positionoutq(){Positionout;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;returnout;}voidFi

15、nd_path(){Positionoffset[4];Positionhere={start.row,start.col};Positionnbr={0,0};intnum_of_nbrs=4;inti,j;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;//上if((start.row==end.row)&&(start.col==end.col)){pa

16、th_len=0;return;}while(1){for(i=0;i

17、是否到达目标位置finishbreak;if(team_l==NULL)//或节点队列是否为空{cout<<"没有结果!!!";return;}here=outq();}path_len=a[end.row][end.col];here=end;for(j=path_len-1;j>=0;j--)//往回找路径{path[j]=here;for(i=0;i