roadsearch.cpp

一个迷宫求解的完整程序

// RoadSearch.cpp: implementation of the RoadSearch class.
//
//////////////////////////////////////////////////////////////////////

#include "RoadSearch.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

RoadSearch::RoadSearch()
{
  
}

RoadSearch::~RoadSearch()
{

}
////////////////////////////////////////////////////////////////////
//
Status RoadSearch::search(Labyrinth &L,Position first,Position end)
{
	RoadNode n,temp;//定义存储位置的中间变量
	n.x=first.x;n.y=first.y;n.di=1;

	do{
        if(n.ifpass(L))
		{//如果当前位置可通，
			s_obj.push(n);//当前路径块入栈
			temp=n.NextPos();//找到下一个路径块作为当前路径块		    
		    L[n.x][n.y]='>';//在迷宫上标示可通的符号'>'
		    if(n.x==end.x&&n.y==end.y)
			   return OK;//如果找到出口，返回		   
		    n=temp;		   
		}
		else{//如果不可通
			if(!s_obj.empty())
			{
				s_obj.pop(temp);//栈顶元素出栈，作为当前路径块
				while(temp.di==5&&!s_obj.empty())
				{//如果所有的相邻路径块都已经搜索
					L[temp.x][temp.y]='#'; //将当前路径标示为不可通符号'#'
					s_obj.pop(temp);//c出栈
				}
				if(temp.di<5)
				{//如果还有没有搜索到的相邻块
					n=temp.NextPos();//找到下一个相邻块并赋给n
					s_obj.push(temp);//将当前路径块入栈
					
				}
			}			 
		}
	}while(!s_obj.empty());
	cout<<"no road to exit..."<<endl;//如果栈空说明没有路径
	return ERROR;
}
/////////////////////////////////////////////////////////////////
 void RoadSearch::Display(Labyrinth &L)
 {	 
     for(int i=0;i<8;i++)
	 {
		 for(int j=0;j<8;j++)
			 cout<<L[i][j]<<"  ";
		 cout<<"\n";
	 }
	 if(!s_obj.empty())//如果栈不空输出栈内元素所在迷宫上的位置
	      s_obj.Display(L);
 }