C++链栈实现迷宫问题

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