mazestack.cpp

关于迷宫问题的几种解法

//
//**********************程序说明*******************************
//			该程序是迷宫问题栈求解的C语言代码，
//			该程序包含两模块,其一是栈的实现,其二是迷宫求解算法的实现
//			这一模块是迷宫求解算法的实现
//			迷宫二维数组表示，初值与教材图3.4一致
//			wjluo，2004年3月4日
//*************************************************************
//

#include <stdio.h>
#include "StackImplement.h"


//**********************迷宫定义**********************//
//用二维数组maze[m+2][p+2]表示迷宫
//maze[i][j]=0表示该位置是墙壁，
//maze[i][j]=1表示该位置是通路
//maze[1][1]为入口
//maze[m][p]为出口
#define m 8  //迷宫宽度
#define p 8  //迷宫长度
short int maze[m+2][p+2]={  {0,0,0,0,0,0,0,0,0,0},
							{0,1,1,0,1,1,1,0,1,0},
							{0,1,1,0,1,1,1,0,1,0},
							{0,1,1,1,1,0,0,1,1,0},
							{0,1,0,0,0,1,1,1,1,0},						
							{0,1,1,1,0,1,1,1,1,0},
							{0,1,0,1,1,1,0,1,1,0},
							{0,1,0,0,0,1,0,0,1,0},
							{0,0,1,1,1,1,1,1,1,0},
							{0,0,0,0,0,0,0,0,0,0}  };	


//***********************标志矩阵定义*********************//
//为防止重走原路，设置一个标志矩阵mark[m+2][p+2]
//所有元素初始化为0，当走到迷宫的该位置[i][j]时，将mark[i][j]置"1"
short int mark[m+2][p+2]={  {0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0},
							{0,0,0,0,0,0,0,0,0,0}   };

//***********************函数PrintPath(SqStack S);***********//
//函数功能：打印路径
//函数参数：栈S
//返回值：返回0表示空栈栈无路径，否则返回1
short int PrintPath(SqStack &S){
	SElemType e;

	if(StackEmpty(S)) return 0;
	
	SqStack tempS;
	InitStack(tempS);
	while(!StackEmpty(S)){
		Pop(S,e);
		Push(tempS,e);
	}
	printf("Get path:\n");
	while(!StackEmpty(tempS)){
		Pop(tempS,e);
		printf("%d,%d\n",e.seat.x ,e.seat.y );
	}
	return 1;
}

//***********************函数MazeStack(int x, int y)***********//
//函数功能：迷宫问题的栈求解算法
//          从迷宫的某一位置Start开始，寻找通向出口end的一条路径。
//函数参数：PositionType start, PositionType end分别表示入口和出口
//返回值：返回0表示未找到路径，返回1表示找到路径
int MazeStack(PositionType start, PositionType end){

	SElemType e;
	SqStack S;
	InitStack(S);  //初始化一个空栈
	
	PositionType  curpos=start;		//设定“当前位置”为“入口位置”
	int curstep=1;

	do{
		if( maze[curpos.x][curpos.y] && !mark[curpos.x][curpos.y]){ 
			//maze[curpos.x][curpos.y] && !mark[curpos.x][curpos.y]对应书上的Pass(curpos)

			mark[curpos.x][curpos.y]=1;
			//表记该位置已走过，对应书上的FootPrint(curpos)

			e.ord=curstep; e.seat=curpos; e.di=1;
			Push(S,e);
			if ( curpos.x ==end.x && curpos.y==end.y ){
				PrintPath(S);
				DestroyStack(S);
				return true;			
			}
			curpos.y =curpos.y+1; //右边位置，curpos.x=curpos.x不变
			curstep++;
		}//if
		else{//当前位置不能通过
			if( !StackEmpty(S) ){
				Pop(S,e);
				while(e.di==4 && !StackEmpty(S) ){
					maze[curpos.x][curpos.y]=0; Pop(S,e);
				}//while
				if(e.di <4){
					e.di++;
					Push(S,e);
					curpos=e.seat;
					switch(e.di){
						case 2: curpos.x++; break;
						case 3: curpos.y--; break;
						case 4: curpos.x--; break;
					}//switch
				}//if
			}//if
		}//else
	}while(!StackEmpty(S));

	DestroyStack(S);
	return false;
}//MazeStack


//主函数：调用迷宫求解的递归算法MazeStack((1,1),(8,8))从入口开始寻找路径
int main(int argc, char* argv[])
{
	PositionType start,end;
	start.x=start.y=1;
	end.x=end.y=8;

    MazeStack(start,end);
	return 0;
}