mazerecursiontotalpath.cpp

关于迷宫问题的几种解法

//
//**********************程序说明*******************************
//			该程序是迷宫问题递归求解全部路径的C语言代码，
//			迷宫二维数组表示，初值与教材图3.4一致
//			wjluo，2004年3月3日
//*************************************************************
//

#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}   };

//***********************两个全局变量************************//
int PathNo=0;	//路径数
SqStack PathS;	//用于存储路径的栈PathS

//***********************函数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 %d:  ", ++PathNo);
	while(!StackEmpty(tempS)){
		Pop(tempS,e); Push(S,e);
		printf("%d,%d  ",e.x ,e.y );
	}
	printf("\n");
	return 1;
}


//***********************函数MazeRecursion(int x, int y)***********//
//函数功能：迷宫求解的递归算法，求解全部路径
//          从迷宫的某一位置[i][j]开始，寻找通向出口[p][m]的一条路径。
//		    如果找到路径，则函数返回1；否则函数返回0。
//			最开始的试探出发点应为入口，即[1][1]
//函数参数：int x, int y分别表示迷宫的某一位置
//返回值：返回0表示未找到路径，返回1表示找到路径
int MazeRecursion(int x, int y){
	SElemType e;
	e.x=x; e.y=y;

	//已到出口，打印路径，返回“1”
	if( (m==x)&&(p==y) ){
		Push(PathS,e);	PrintPath(PathS);	Pop(PathS,e); return 1;
	}
	
	//如果该位置是墙，返回0
	if(!maze[x][y]) return 0;

	//表记该位置已走过
	mark[x][y]=1;
	Push(PathS,e);

	//既然该位置是通路，则每个位置有4个方向可以走，每个方向都要试一下
	//如果某方向的下一个位置未标记（即不在当前路径路上），则继续往前走
	if( !mark[x][y+1] ) MazeRecursion(x,y+1);  //向右
	if( !mark[x+1][y] ) MazeRecursion(x+1,y);  //向下
	if( !mark[x][y-1] ) MazeRecursion(x,y-1);  //向左
	if( !mark[x-1][y] ) MazeRecursion(x-1,y);  //向上

	mark[x][y]=0;
	Pop(PathS,e);
	return 0;
}


//主函数：调用迷宫求解的递归算法MazeRecursion(1,1)从入口开始寻找全部路径
int main(int argc, char* argv[])
{
	InitStack(PathS);
    MazeRecursion(1,1);
	DestroyStack(PathS);
	return 0;
}