迷宫算法实现.cpp

C++的一些简单代码 希望能给初学者带来小小的帮助

#include<iostream>
using std::cout;
using std::endl;

#define XS 0
#define YS 2
#define XM 6
#define YM 6
#define XE 5
#define YE 1
int mazelab[YM][XM]={
	{1,1,1,1,1,1},
	{1,1,0,0,0,0},
	{0,0,0,1,0,1},
	{1,0,1,1,1,1},
	{1,0,0,0,0,1},
	{1,1,1,1,1,1}
};
int flags[YM][XM]={0};
bool search(int,int,char);

void main(){
	int i,j;
	mazelab[YS][XS]=-1;
	if(search(XS,YS,'E'))		//从左边入口开始往东进行搜索.
	{
		/*MessageBox("搜索迷宫路径成功,路径如红色所示!","成功提示",MB_OK);
		CMazesDlg::setcolor(XS,YS);	//从左边入口处开始画路线.
		success=true;		//搜索成功*/
		cout<<"迷宫图:1代表墙,0代表路,入口是("<<XS<<","<<YS<<"),出口是("<<XE<<","<<YE<<")"<<endl
			<<"-1是向东走,-2是向南走,-3是向西走,-4是向北走"<<endl;
		for(i=0;i<YM;i++){
			for(j=0;j<XM;j++){
				cout<<mazelab[i][j]<<' ';
			}
			cout<<endl;
		}

		cout<<endl<<"1代表分支"<<endl;
		for(i=0;i<YM;i++){
			for(j=0;j<XM;j++){
				cout<<flags[i][j]<<' ';
			}
			cout<<endl;
		}

		cout<<endl<<"9代表出路"<<endl;
		int x=XS;
		int y=YS;
		int temp;
		while(x!=XE+1||y!=YE){
			temp=mazelab[y][x];
			do{
				if(x==XE+1&&y==YE) break;
				switch(temp){
				case -1:mazelab[y][x]=9;x++;break;
		        case -2:mazelab[y][x]=9;y++;break;
				case -3:mazelab[y][x]=9;x--;break;
				case -4:mazelab[y][x]=9;y--;break;
				}
			}while(mazelab[y][x]==0);
		}
		for(i=0;i<YM;i++){
			for(j=0;j<XM;j++){
				cout<<mazelab[i][j]<<' ';
			}
			cout<<endl;
		}
	}
	else cout<<"No way out!"<<endl;

}

bool search(int x,int y,char dir)   //dir 表示搜索方向
{
	bool subway=false,noway=false,east=false,west=false,north=false,south=false;
	//subway 表示是否有左右方向的分杈子路，noway 表示是否可以继续往前走。
	//east ,west, south, north 分别表示是否有往东，西，南，北的分叉子路
	while(!subway && !noway)
	{
		switch(dir)
		{
		 case 'E':  		//往东走，在图中即为往右走。
			x++;
			if(x==XM-1) noway=true;	
		//检测是否越界。以下三句为检测是否有往前，往右，往左分叉子路，下同。
			if(x<(XM-1) && mazelab[y][x+1]){
				noway=true,east=false;
			} else 
				east=true;
				
			if(y<(YM-1) && !(mazelab[y+1][x])){
				south=true,subway=true;
			}
			if(y>0 && !(mazelab[y-1][x])){
				north=true,subway=true;
			}

			if(x==XE && y==YE) return true;	//到达终点，成功返回。

			break;
		 case 'W':  		//往西走，在图中即为往左走。
			x--;   
			if(x==0) noway=true;
			if(x>0 && mazelab[y][x-1]){
				noway=true,west=false;
			} else 
				west=true;
			if(y<(YM-1) && !(mazelab[y+1][x])){
				south=true,subway=true;
			}
			if(y>0 && !(mazelab[y-1][x])){
				north=true,subway=true;
			}

			if(x==XE && y==YE) return true;	//到达终点，成功返回。

			break;
		 case 'S':  		//往南走，在图中即为往下走。
			 y++;
		 	if(y==YM-1) noway=true;
			if(y<(YM-1) && mazelab[y+1][x]){
				noway=true,south=false;
			} else 
				south=true;
			if(x<(XM-1) && !(mazelab[y][x+1])){
				east=true,subway=true;
			}
		 	if(x>0 && !(mazelab[y][x-1])){
		 		west=true,subway=true;
		 	}

			if(x==XE && y==YE) return true;	//到达终点，成功返回。

			break;
		 case 'N':  		//往北走，在图中即为往上走。
			 y--;
		 	if(y==0) noway=true;
			if(y>0 && mazelab[y-1][x]){
				noway=true,north=false;
			} else 
				north=true;
			if(x<(XM-1) && !(mazelab[y][x+1])){
				east=true,subway=true;
			}
		 	if(x>0 && !(mazelab[y][x-1])){
		 		west=true,subway=true;
		 	}

			if(x==XE && y==YE) return true;	//到达终点，成功返回。

			break;
		}//edn switch
	}//end while

	if(!subway && noway) return false ; 	
	//前进方向无路可走且没有左右分叉子路，返回失败，即此路不通。
	if(!flags[y][x]) 
		flags[y][x]=1;
	 	//迷宫中往往有回路，在分叉路口作标记
		//表示已经来过，防止程序在此转圈，无限迭代而失败。
	else 
		return false ; 	
	//标记为1，表示已经来过此处，返回失败，即此路不通。
	if(subway)			//存在分叉子路，迭代搜索。
	{
		if(east)  east=search(x,y,'E');	 //有往东的子路，继续往东搜索。
		if(south) south=search(x,y,'S');	 //有往南的子路，继续往南搜索。
		if(west)  west=search(x,y,'W');	 //有往西的子路，继续往西搜索。
		if(north) north=search(x,y,'N');	 //有往北的子路，继续往北搜索。
	}		
	//根据在分叉路口的是否成功迭代返回作标记方向，后面根据此标记方向画路径
	if(east)  mazelab[y][x]=-1;		// -1表示在此分叉路口往东走可以走到出口，
	if(south) mazelab[y][x]=-2;		// -2 表示在此分叉路口往南走可以走到出口，
	if(west)  mazelab[y][x]=-3;		// -3表示在此分叉路口往西走可以走到出口，
	if(north) mazelab[y][x]=-4;		// -4表示在此分叉路口往北走可以走到出口。
	 return (east||west||south||north) ;		//返回此分叉路口的最终搜索结果。
}