#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <stdlib.h>
#define NULL 0
#define LG sizeof(struct Stack) /*定义结构体的长度*/
struct Stack{
int x; /*迷宫中的X坐标*/
int y; /*迷宫中的Y坐标*/
struct Stack *next;
struct Stack *pre; /*定义向上的指针,为了最后正序输出堆栈*/
};
struct Stack *top; /*定义堆栈的头指针*/
struct Stack *base; /*定义堆栈的尾指针*/
struct Stack * initstack(){ /*初始化堆栈,并在栈底放入0,0*/
base = top = ( struct Stack *) malloc ( LG );
top->x = 0;
top->y = 0;
top->next = NULL;
top->pre = NULL;
return top;
}
struct Stack * push( int x , int y ){ /*往堆栈中压入数据*/
struct Stack *p;
p = top;
top = ( struct Stack *) malloc ( LG );
top->next = p;
p->pre = top;
top->x = x;
top->y = y;
return top;
};
int x_max,y_max; /*用户输入的矩阵宽度和高度*/
int mazesiae[100][100]; /*定义矩阵(最大为100*100)*/
int * get(int array[2]){ /*从堆栈中取出数据,并释放栈顶的空间*/
struct Stack *p;
if(top == base) return 0;
else{
array[0] = top->x;
array[1] = top->y;
p = top;
top = top->next;
top->pre = NULL;
free(p);
}
return &array[0];
}
int * readfree(int array[2]){ /*为了最后正序输出堆栈定义的函数,从栈底向栈顶读数据,并释放栈底空间*/
struct Stack *p;
if(top == base) return 0;
else{
p = base;
base = base->pre;
base->next = NULL;
array[0] = base->x;
array[1] = base->y;
free(p);
}
return &array[0];
}
int position(){ /*判断现在的坐标是否在堆栈中存在*/
struct Stack *p;
p = top;
if( p->x==0 && p->y==0 ) return 0;
while( p!= base ){
p = p->next;
if( p->x == top->x && p->y == top->y ) return 1;
}
return 0;
}
void search(int array_pre[2]){ /*搜索迷宫中的路径*/
int array[2];
array[0] = top->x;
array[1] = top->y;
//到达终点,则跳出
if( top->x == x_max-1 && top->y == y_max-1 ){
return;
}
//向上走,递归
if( ( top->x - 1 >=0 && mazesiae[top->x - 1][top->y] == 0) && ( top->x - 1 != array_pre[0] || top->y != array_pre[1] ) && !( top->x == x_max-1 && top->y == y_max-1 ) && !position() ){
top = push( top->x - 1 , top-> y );
search(array);
}
//向下走,递归
if( ( top->x + 1 < x_max && mazesiae[top->x + 1][top->y] == 0) && ( top->x + 1 != array_pre[0] || top->y != array_pre[1] ) && !( top->x == x_max-1 && top->y == y_max-1 ) && !position() ){
top = push( top->x + 1 , top->y );
search(array);
}
//向左走,递归
if( ( top->y - 1 >=0 && mazesiae[top->x][top->y - 1] == 0) && ( top->x != array_pre[0] || top->y - 1 != array_pre[1] ) && !( top->x == x_max-1 && top->y == y_max-1 ) && !position() ){
top = push( top->x , top->y - 1 );
search(array);
}
//向右走,递归
if( ( top->y + 1 < y_max && mazesiae[top->x][top->y + 1] == 0) && ( top->x != array_pre[0] || top->y + 1 != array_pre[1] ) && !( top->x == x_max-1 && top->y == y_max-1 ) && !position() ){
top = push( top->x , top->y + 1 );
search(array);
}
//如果四个方向都不能走,则退回上一步,取出栈顶的值
if( !(top->x == x_max-1 && top->y == y_max-1) ) get( array );
return;
}
void createmaze() /*随机生成矩阵*/
{
int i,j,temp;
srand((unsigned) time(NULL));
for(i=0;i<x_max;i++){
for(j=0;j<y_max;j++){
temp = rand()%10;
mazesiae[i][j] = ( temp < 7 ) ? 0 : 1; /* 7/10 为0 , 3/10 为1*/
}
}
}
void printmaze(){
int i,j;
for(i=0;i<x_max;i++){ /*输出随机生成的矩阵*/
for(j=0;j<y_max;j++){
printf("%2d ",mazesiae[i][j]);
}
printf("\n");
}
printf("\n\n");
}
void main(void){
int array[2]; /*定义一个数组存放坐标,初始化的值没有意义*/
int * p; /*定义辅助的指针*/
do{ /*要求用户输入矩阵大小,如果小于等于1则再次要求用户输入*/
printf("\n *****请输入迷宫的规格 *****\n");
printf("\n x,y [ x>1 and y>1 ]\n");
scanf("%d,%d",&x_max,&y_max);
}while(x_max<=1 && y_max<=1);
do{
createmaze();
mazesiae[0][0] = 0; /*定义起点为0*/
mazesiae[x_max-1][y_max-1] = 0; /*定义终点为0*/
printf("**随机迷宫图是** \n\n");
printmaze();
top = initstack(); /*初始话堆栈*/
top = push(0,0); /*压入起点的坐标*/
search( array ); /*寻找路径走出迷宫*/
if(top->x != x_max -1 || top->y != y_max -1){ /*如果top指针没有指到终点,则是没有路出迷宫*/
printf(" 被困迷宫,无路逃脱 T_T\n\n\n");
}
else{
printf("迷宫正确路径 :\n"); /*如果有路出迷宫则正序输出堆栈中的坐标*/
while( base!=top ){
p = readfree(array);
printf(" (%d,%d) ",p[0],p[1]);
if( base!=top ) printf("-->");
}
free(base);
break;
}
free(base); /*释放堆栈空间*/
}while( !(top->x == x_max-1 && top->y == y_max-1) );
printf("\n");
}