C++链栈达成迷宫问题
发布时间：2021-11-24 19:27:24 所属栏目：教程 来源：互联网
导读：//CPath.h 文件 #includeiostream #includefstream using namespace std; class CPath //应用程序类 { public: int m[50][50]; void Initpath(int jshux,int jshuy,int qshu); int path(int beginx,int beginy,int endx,int endy); void output(int x,int y);
|
//CPath.h 文件 #include<iostream> #include<fstream> using namespace std; class CPath //应用程序类 { public: int m[50][50]; void Initpath(int jshux,int jshuy,int qshu); int path(int beginx,int beginy,int endx,int endy); void output(int x,int y); }; struct Node // { int x; int y; }; typedef struct stack // 链栈 { int di; struct Node seat; stack *next; }*pstack; void Push(pstack &top,stack &c) { stack *s=new(stack); s->di=c.di; s->seat=c.seat; s->next=top; top=s; } int Pop(pstack &top,stack &c) { if(top==NULL) return 0; stack *p; c.di=top->di; c.seat=top->seat; p=top; top=top->next; delete(p); return 1; } // CPath.cpp 文件 #include<iostream> using namespace std; #include<iomanip> #include"CPath.h" void CPath::Initpath(int jshux,int jshuy,int qshu) //初始化迷宫 { int i,j,x1,y1; int x=jshux; int y=jshuy; for(i=0;i<x+2;i++) { m[i][0]=0; m[i][jshux+1]=0; } for(i=0;i<y+2;i++) { m[0][i]=0; m[y+1][i]=0; } for(i=1;i<x+1;i++) for(j=1;j<y+1;j++) m[i][j]=1; j=qshu; ifstream ccin("data.txt",ios::in); cout<<"是否从data.txt读入迷宫内每个内墙的行数和列数 (Y//N) "; char p; cin>>p; if(p=='Y') { for(i=1;i<=j;i++) { ccin>>x1>>y1; m[x1][y1]=0; } } else { cout<<"手动输入迷宫内每个内墙的行数和列数:"; for(i=1;i<=j;i++) { ccin>>x1>>y1; m[x1][y1]=0; } } } int CPath::path(int beginx,int beginy,int endx,int endy) { int ccx,ccy; int dti[]={0,1,0,-1}; int dtj[]={1,0,-1,0}; ccx=beginx; ccy=beginy; struct stack *s=new(stack); s->next=NULL; struct stack e; e.next=NULL; int step=1; do { if(m[ccx][ccy]==1) { m[ccx][ccy]=step; e.seat.x=ccx; e.seat.y=ccy; e.di=0; Push(s,e); step++; if(ccx==endx&&ccy==endy) return 1; ccx+=dti[e.di]; ccy+=dtj[e.di]; } else { if(s->next) { Pop(s,e); step--; while(e.di==3&&s->next) { m[e.seat.x][e.seat.y]=-1; Pop(s,e); step--; } if(e.di<3) { e.di++; Push(s,e); step++; ccx=e.seat.x; ccy=e.seat.y; ccx+=dti[e.di]; ccy+=dtj[e.di]; } } } }while(s->next); return 0; } void CPath::output(int x,int y) { for(int i=0;i<x+2;i++) { for(int j=0;j<y+2;j++) cout<<setw(3)<<m[i][j]; cout<<endl; } } int main() { int jshux,jshuy,qshu,beginx,beginy,endx,endy; cout<<"jshux and jshuy:"; cin>>jshux>>jshuy; cout<<"qshu:"; cin>>qshu; CPath mmm; mmm.Initpath(jshux,jshuy,qshu); cout<<"迷宫："<<endl; mmm.output( jshux,jshuy); cout<<"beginx and beginy:"; cin>>beginx>>beginy; cout<<"endx and endy:"; cin>>endx>>endy; if(mmm.path(beginx,beginy,endx,endy)) { cout<<"路线："<<endl; mmm.output(jshux,jshuy); } else cout<<"没有路径！"; return 0; }  （编辑：济南站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
