迷宫求解(全部解).txt

很高兴成为这里的一员,我将继续努力,多多上传好的代码,文件里有一些自己写的,也有一些收集的程序,基本上都有解释.

共有三个文件maze.h  mclass.cpp  t3.cpp

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

#define stackinitsize 50
#define stackincrease 10
#define E 0
#define END 4
#define way 0
#define wall 1

typedef struct po
{
 int x;
 int y;
}po;
typedef struct Em
{
 po seat;
 int di;
}Em;

class ST
{
private:
 Em *base;
 Em *top;
 int stacksize;
public:
 ST(Em *b=NULL,Em *t=NULL,int s=0)
 {
  base=b;top=t;stacksize=s;
 }
 void init();
 void push(Em e);
 void di_add();
 int  gettop(Em &e);
 int  pop(Em &e);
 ~ST(){free(base);}
};

/**********************************************mclass.cpp******************************/

#include "maze.h"
void ST::init()
{
 if(!(base=(Em *)malloc(stackinitsize*sizeof(Em))))
  exit(0);
 top=base;
 stacksize=stackinitsize;
}
void ST::push(Em e)
{
 if((top-base)>=stacksize)
 {
  base=(Em *)realloc(base,(stacksize+stackincrease)*sizeof(Em));
  if(base==NULL) exit(0);
  top=base+stacksize;
  stacksize+=stackincrease;
 }
 *top++=e;
}
void ST::di_add()
{
 (top-1)->di+=1;
}
int ST::gettop(Em &e)
{
 if(top==base) return 0;
 e=*(top-1);
 return 1;
}
int ST::pop(Em &e)
{
 if(top==base) return 0;
 top-=1;
 e=*top;
 return 1;
}


/************************************************t3.cpp**************************/

#include "maze.h"
const int m=8;
const int n=11;
const po direction[4]={{0,1},{1,0},{0,-1},{-1,0}};
int maze[m][n];
void main()
{
 void initmaze();
 void findway();
 initmaze();
 findway();
// delete[] maze;
}
void creatwall()
{
// int *p;
// p=(int *)malloc(m*n*sizeof(int));
 for(int i=0;i<m;i++)
  for(int j=0;j<n;j++)
   maze[i][j]=wall;
// return p;
}
void initmaze()
{
 int i,j;
 char c;
 cout<<"Load default maze[Y/N]Y\b";
 c=cin.get();
 if(c==10) c='y';
 else while(c!='y'&&c!='Y'&&c!='n'&&c!='N')
 {
  cout<<"Enter Y or N:";
  cin>>c;
 }
 if(c=='y'||c=='Y')
 {
//  m=8;
//  n=11;
  creatwall();
  maze[1][1]=maze[1][3]=maze[1][4]=maze[1][8]=maze[1][9]=way;
  for(i=1;i<6;i++) maze[2][i]=way;
  maze[2][7]=maze[2][8]=way;
  maze[3][1]=way;
  for(i=5;i<9;i++) maze[3][i]=way;
  for(i=1;i<4;i++) maze[4][i]=way;
  maze[4][5]=maze[4][8]=way;
  maze[5][2]=maze[5][3]=maze[5][5]=maze[5][8]=maze[5][9]=way;
  for(i=3;i<10;i++) maze[6][i]=way;

  cout<<"The maze:\n\t";
  for(i=0;i<n;i++)
   cout<<setw(3)<<i;
  cout<<"\n"<<endl;
  for(int l=0,j=0;l<m;l++,j++)
  {
   cout<<setw(4)<<j<<"\t";
   for(int k=0;k<n;k++)
    cout<<setw(3)<<maze[l][k];
   cout<<"\n";
  }
 }
 else
 {
//  cout<<"Input m & n:"<<endl;
//  cin>>m>>n;
  creatwall();
  cout<<"\n"<<"\t";
  for(j=0;j<n;j++) cout<<setw(3)<<j;
  cout<<"\n"<<endl;
  for(i=0;i<m;i++)
  {
   cout<<setw(4)<<i<<"\t";
   for(j=0;j<n;j++)
    cout<<setw(3)<<maze[i][j];
   cout<<endl;
  }
  cout<<"Enter 0 to exit."<<endl;
  while(1)
  {
   cout<<"Input the path coordinate:"<<endl;
   do
   {
    cin>>i;
   }while(i<0||i>m-2);
   if(i==0) break;
   do
   {
    cin>>j;
   }while(j<0||j>n-2);
   if(j==0) break;
   maze[i][j]=way;
  }
  while(cin.get()!=10); //清空缓存
 }
}
void findway()
{
 Em e;
 po begin={1,1},end={6,9},step;
 int i=1,count=1;
 cout<<"load default start/exit point?(1,1)(6,1)"<<endl;

 if(cin.get()!=10) //输入不是回车
 {
  do
  {
   cout<<"Input the start point:";
   cin>>begin.x>>begin.y;
   cout<<"Input the exit point:";
   cin>>end.x>>end.y;
  }while(begin.x>m-2||begin.y>n-2||end.x>m-2||end.y>n-2);
 }

 ST stack;

 stack.init();
 step=e.seat=begin;
 e.di=E;
 stack.push(e);
 maze[begin.x][begin.y]=i++;
 while(1)
 {
  while(e.di!=END)
  {
   step.x+=direction[e.di].x;
   step.y+=direction[e.di].y;
   if(maze[step.x][step.y]==way)
   {
    e.seat=step;
    e.di=E;
    maze[step.x][step.y]=i++;
    stack.push(e);
    //出口
    if(step.x==end.x&&step.y==end.y)
    {
     cout<<"The "<<count++<<" path is:"<<endl;
     for(int j=0;j<m;j++)
     {
      cout<<"\t";
      for(int k=0;k<n;k++)
       cout<<setw(3)<<maze[j][k];
      cout<<"\n";
     }
     break;
    }
   }
   else
   {
    stack.di_add();
    stack.gettop(e);
    step=e.seat;
   }
  }
  stack.pop(e);
  step=e.seat;
  maze[step.x][step.y]=way;
  if(!stack.gettop(e)) break;
  stack.di_add();
  e.di++;
  step=e.seat;
  i--;
 }
 if(count==1) cout<<"No answer!"<<endl;
}


/////////////////////////考虑到C++标准库中有关于栈的库，写了如下代码调用标准库，可代替上面的程序：

#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
using namespace std;
#define E 0
#define END 4
#define way 0
#define wall 1
typedef struct
{
 int x;
 int y;
}po;
typedef struct
{
 po seat;
 int di;
}Em;

const int m=8;
const int n=11;
const po direction[4]={{0,1},{1,0},{0,-1},{-1,0}};
int maze[m][n];
void main()
{
 void initmaze();
 void findway();
 initmaze();
 findway();
}
void creatwall()
{
 for(int i=0;i<m;i++)
  for(int j=0;j<n;j++)
   maze[i][j]=wall;
}
void initmaze()
{
 int i,j;
 char c;
 cout<<"Load default maze[Y/N]Y\b";
 c=cin.get();
 if(c==10) c='y';
 else while(c!='y'&&c!='Y'&&c!='n'&&c!='N')
 {
  cout<<"Enter Y or N:";
  cin>>c;
 }
 if(c=='y'||c=='Y')
 {
  creatwall();
  maze[1][1]=maze[1][3]=maze[1][4]=maze[1][8]=maze[1][9]=way;
  for(i=1;i<6;i++) maze[2][i]=way;
  maze[2][7]=maze[2][8]=way;
  maze[3][1]=way;
  for(i=5;i<9;i++) maze[3][i]=way;
  for(i=1;i<4;i++) maze[4][i]=way;
  maze[4][5]=maze[4][8]=way;
  maze[5][2]=maze[5][3]=maze[5][5]=maze[5][8]=maze[5][9]=way;
  for(i=3;i<10;i++) maze[6][i]=way;

  cout<<"The maze:\n\t";
  for(i=0;i<n;i++)
   cout<<setw(3)<<i;
  cout<<"\n"<<endl;
  for(int l=0,j=0;l<m;l++,j++)
  {
   cout<<setw(4)<<j<<"\t";
   for(int k=0;k<n;k++)
    cout<<setw(3)<<maze[l][k];
   cout<<"\n";
  }
 }
 else
 {
  creatwall();
  cout<<"\n"<<"\t";
  for(j=0;j<n;j++) cout<<setw(3)<<j;
  cout<<"\n"<<endl;
  for(i=0;i<m;i++)
  {
   cout<<setw(4)<<i<<"\t";
   for(j=0;j<n;j++)
    cout<<setw(3)<<maze[i][j];
   cout<<endl;
  }
  cout<<"Enter 0 to exit."<<endl;
  while(1)
  {
   cout<<"Input the path coordinate:"<<endl;
   do
   {
    cin>>i;
   }while(i<0||i>m-2);
   if(i==0) break;
   do
   {
    cin>>j;
   }while(j<0||j>n-2);
   if(j==0) break;
   maze[i][j]=way;
  }
  while(cin.get()!=10); //清空缓存
 }
}
void findway()
{
 Em e;
 po begin={1,1},end={6,9},step;
 int i=1,count=1;
 cout<<"load default start/exit point?(1,1)(6,1)"<<endl;

 if(cin.get()!=10) //输入不是回车
 {
  do
  {
   cout<<"Input the start point:";
   cin>>begin.x>>begin.y;
   cout<<"Input the exit point:";
   cin>>end.x>>end.y;
  }while(begin.x>m-2||begin.y>n-2||end.x>m-2||end.y>n-2);
 }

 stack<Em,vector<Em> >stackm;

 step=e.seat=begin;
 e.di=E;
 stackm.push(e);
 maze[begin.x][begin.y]=i++;
 while(1)
 {
  while(e.di!=END)
  {
   step.x+=direction[e.di].x;
   step.y+=direction[e.di].y;
   if(maze[step.x][step.y]==way)
   {
    e.seat=step;
    e.di=E;
    maze[step.x][step.y]=i++;
    stackm.push(e);
    //出口
    if(step.x==end.x&&step.y==end.y)
    {
     cout<<"The "<<count++<<" path is:"<<endl;
     for(int j=0;j<m;j++)
     {
      cout<<"\t";
      for(int k=0;k<n;k++)
       cout<<setw(3)<<maze[j][k];
      cout<<"\n";
     }
     break;
    }
   }
   else
   {
    e=stackm.top();
    e.di++;
    step=e.seat;
    stackm.pop();
    stackm.push(e);
//    stackm.di_add();
//    stackm.gettop(e);
//    step=e.seat;
   }
  }
  e=stackm.top();
  stackm.pop();
  step=e.seat;
  maze[step.x][step.y]=way;
  if(stackm.empty()) break;
  e=stackm.top();
  stackm.pop();
  e.di++;
  stackm.push(e);
  step=e.seat;
  i--;
 }
 if(count==1) cout<<"No answer!"<<endl;
}