mazerecursion.cpp

关于迷宫问题的几种解法

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

#include <stdio.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}   };


//***********************函数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){
	int bGetPath=0;

	//已到出口，返回“1”
	if( (m==x)&&(p==y) ){
		printf("%d,%d\n",x,y);
		return 1;
	}
	
	//表记该位置已走过
	mark[x][y]=1;

	//如果该位置是墙，返回0
	if(!maze[x][y]) return 0;

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

	if(bGetPath){
		printf("%d,%d\n",x,y);
		return 1;
	}
	
	return 0;
}


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