C++鏈棧實現迷宮問題

//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;
}