利用回溯法解决迷宫问题

/*
♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀
♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂
 ● Date  :2011-11-16    
 ● Author :renlimin
 ● Description  : 

 ● subscribe:    
 
 ● Introduction： 
 ●                             

♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀♀
♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂♂
*/
//----------------包含头文件---------------------------------
#include“stdio.h“ 
#include“stdlib.h“
#include“time.h“

//=--------------定义常量-------------------------------------
#define  max 126 
#define MaxSize 10000
//---------------自定义数据类型-------------------------------
typedef struct
{
	int x; // 横 坐标 
	int y; // 纵 坐标 
	int k; // 方 向
}datatype; //定义栈元素类型

typedef struct 
{
	datatype data[MaxSize];
	int top;
}STACK;//定义栈类型

typedef  struct            
{ 
	int x;
	int y;
} item ;//定义方向数据的型  
 
//---------------变量定义-------------------------------------
int hanglie;
int Maze[max+2][max+2];
int Mark[max+2][max+2];
STACK road;
item move[8];
//---------------基本函数声明---------------------------------
int Rand_01（int s_hangint s_lie）;
void InitStack（STACK *S）;
//---------------函数声明-------------------------------------
void Init_value（void）;
int Go（int *mazeint HANGint LIE）;
void Random_Maze（void）;//随机生成迷宫
int Push（STACK *Sdatatype x）;
int Pop（STACK *Sdatatype *x）;     
int Empty（STACK *S）;
int GetTop（STACK *S datatype *x）;   
void road_line（int hangint lie）;
//###################################################### main #
int main（void）

{
	int selhanglieij;
//	int Maze[hang][lie];
	Init_value（）;
	//生成迷宫1随机生成2输入
do{
	printf（“\n##########################################“）;
	printf（“\n#                  走迷宫                #\n#“）;
	printf（“                                        #“）;
	printf（“\n#    根据提示选择随机或手动输入一迷宫    #\n#“）;
	printf（“                                        #“）;
	printf（“\n#    1 随机生成迷宫 2 手动输入迷宫 0 OUT #\n“）;
	printf（“ >>“）;
	scanf（“%d“&sel）;
	getchar（）;
	while（sel<0||sel>2）
	{
		printf（“\n!序号必须是01或2，请重新输入>> “）;
		scanf（“%d“&sel）;
		getchar（）;
	}
	if（sel==1）
	{
		printf（“\n输入迷宫的行数>>“）;
		scanf（“%d“&hang）;

		printf（“输入迷宫的行数>>“）;
		scanf（“%d“&lie）;	
		srand（（unsigned int）time（NULL））;//用当前日历时间初始化随机数种子 
		
		for（i=0 ; i		{
			for（j=0 ; j			{
				Maze[i+1][j+1]=rand（）%2;//如果要取得[ab）之间的“int“数，则 num = rand（）%（b-a） + a;
				printf（“%d  “ Maze[i+1][j+1]）;	//printf（“Ten random numbers from 0 to 1\n\n“）;	
			}                               
			printf（“\n“）;
		}
	}
	else
	{
		printf（“\n     手动输入迷宫\n“）;
	}

	
	//走迷宫
	if（Go（&Maze[0][0]hanglie）==1）
	{
		printf（“\n走通\n“）;
		for（i=0;i<=road.top;i++）
			printf（“%d%d  “road.data[i].xroad.data[i].y）;
		printf（“%d%d  “hanglie）;
		//画出轨迹路线
		road_line（hanglie）;
        
		Init_value（）;
	}
	else
	{
		printf（“\n没走通\n“）;
		Init_value（）;
	}
}while（sel!=0）;//do{};

	return 0;
}
/*--------