maze.cpp

利用回溯法求解迷宫问题

# define Stack_Max  40  //使用顺序链表top指向最高位(有元素)的下一位
//# include "header.h"

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

int curstep=1;
struct Position
{
	int x;
	int y;
};
struct MazeType
{
	Position seat;
	int dir;
	int order;
};

struct SqStack
{
	MazeType *top;
	MazeType *base;
	int stacksize;

};


void InitStack(SqStack &s)
{
    	s.base=(MazeType *)malloc(sizeof(MazeType)*Stack_Max);

		if(s.base==NULL)
			exit(-1);

		s.top=s.base;
		s.stacksize=Stack_Max;
}


void DestroyStack(SqStack &s)
{
	free(s.base);
	s.base=s.top=NULL;
	s.stacksize=0;
}


bool StackEmpty(SqStack s)
{
	if(s.base==s.top)
		return true;

	else
          return false;

}


void Push(SqStack &s,MazeType e)
{
  if(s.top-s.base >= s.stacksize)
  {	  s.base=(MazeType *)realloc(s.base,sizeof(MazeType)*(Stack_Max*2));//增加空间
  
      if(!s.base)
		exit(-1);

	  s.top = s.base+s.stacksize;
	  s.stacksize+=s.stacksize;
  }


  *(s.top)++=e;



}




bool Pop(SqStack &s,MazeType &e)
{
	if(s.top==s.base)
		return false;  //为空

	e=*--s.top;
	return true;
}



class MazeProblem
{
private:
	int MazeP[100][100];
	Position start,end;
	Position curpos;
	//int  curstep;
	int row,col;

public:
    //MazeProblem(){ curstep=1; }
	void PrintMaze()
	{	for(int i=0;i<row;i++)
	
	{	for(int j=0;j<col;j++)
			cout<<MazeP[i][j];
             
		cout<<endl;
	}


	}

	void NextPos(Position &p,int dir)
	{
	Position dires[4]={(0,1),(1,0),(0,-1),(-1,0)};
	p.x+=dires[dir].x;
	p.y+=dires[dir].y;
	}

	void InitMaze()
	{
      // curstep=1;
	cout<<"请输入行数,列数(包括外墙)"<<endl;
	cin>>row>>col;

   //	MazeP=new char[row][col];

	for(int i=0;i<row;i++)
	{
		MazeP[0][i]=0;    //制造外墙
		MazeP[row-1][i]=0;
	}

	for(int j=0;j<col;j++)
	{
		MazeP[j][0]=0;
		MazeP[j][col-1]=0;
	}
   

	for(int h=1;h<row-1;h++)
	   for(int k=1;k<col-1;k++)
		   MazeP[h][k]=1;  //1表示能通过


	   int x,y;
	   int num;
	   cout<<"输入障碍个数"<<endl;
	   cin>>num;

	   cout<<"请依次输入每个障碍的坐标"<<endl;
      for(int g=1;g<=num;g++)
	  {
		  cin>>x>>y;
		  MazeP[x][y]=0;
	  }
	  

			  


	 


	   cout<<"你所设置的迷宫如下:"<<endl;
	   PrintMaze();


	   cout<<"输入初始位置(x,y)"<<endl;
      cin>>start.x>>start.y;

	  cout<<" 输入结束位置"<<endl;
	  cin>>end.x>>end.y;




	}

	

	bool Pass(Position p)
	{	
		if(MazeP[p.x][p.y]==1)
		return true;
	else
		return false;

	}

	void MarkFoot(Position p)
	{
		MazeP[p.x][p.y]=curstep;

	}
	void MarkNoWay(Position p)
	{
       MazeP[p.x][p.y]=-1;

	}


	bool MazePath()
	{
	SqStack s;
	//Position curpos;
	MazeType e;
	InitStack(s);
	curpos = start;


	do
	{
		if(Pass(curpos))
		{
			MarkFoot(curpos);
			//留下走过标记
			e.order=curstep;
			e.seat=curpos;
			e.dir=0;
			Push(s,e);
			curstep++;

			if(curpos.x==end.x && curpos.y==end.y)
				return true;

			NextPos(curpos,e.dir);
		}

      else
	  {
             if(!StackEmpty(s))
			 {
				 Pop(s,e);
				 curstep--;
				 while(e.dir==3 && !StackEmpty(s))
				 {
					 MarkNoWay(e.seat);
					 Pop(s,e);
					 curstep--;
				 }

                if(e.dir < 3)
				{
					e.dir++;
					Push(s,e);
					curstep++;
					curpos=e.seat;
					NextPos(curpos,e.dir);
				}

			 }


	  }

	}while(!StackEmpty(s));

	return false;
	}

};



int main()
{
	MazeProblem m;
	m.InitMaze();
	if(m.MazePath())
		m.PrintMaze();
	else
	{

		cout<<"没找到路径"<<endl;
		m.PrintMaze();
	}
    
	return 0;
}