maze.cpp

迷宫算法

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW 0
char maze[10][11]=
{"##########",
 "#  #   # #",
 "#  #   # #",
 "#    ##  #",
 "# ###    #",
 "#   #    #",
 "# #   #  #",
 "# ### ## #",
 "##       #",
 "##########"};
typedef struct{
   int x;
   int y;
}SElemType;
typedef struct{
   SElemType *base;
   SElemType *top;
   int stacksize;
}SqStack;
//初始化顺序栈
int InitStack_Sq(SqStack &S){
   S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!S.base)
	   exit(OVERFLOW);
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;
   return OK;
}
//元素e进栈
int Push_Sq(SqStack &S,SElemType e){
	if(S.top-S.base>=STACK_INIT_SIZE){
	   S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
	   if(!S.base)
		   exit(OVERFLOW);
	   S.top=S.base+S.stacksize;
	   S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return OK;
}
//删除栈顶元素e，即出栈
int Pop_Sq(SqStack &S,SElemType &e){
    if(S.top==S.base) 
		exit(ERROR);
	e=*--S.top;
	return OK;
}
//判断是否可通
int Pass(SElemType cur,int &k){
   if(maze[cur.x][cur.y+1]==' ') {k=26;return 1;}
   else if(maze[cur.x+1][cur.y]==' ') {k=25;return 1;}
   else if(maze[cur.x][cur.y-1]==' ') {k=27;return 1;}
   else if(maze[cur.x-1][cur.y]==' ') {k=24;return 1;}
   else return 0;
}
//设定下一位置是当前位置的相邻块
SElemType NextPos(SElemType cur){
	if(maze[cur.x][cur.y+1]==' ') {cur.y++;return cur;}
	if(maze[cur.x+1][cur.y]==' ') {cur.x++;return cur;}
	if(maze[cur.x][cur.y-1]==' ') {cur.y--;return cur;}
	if(maze[cur.x-1][cur.y]==' ') {cur.x--;return cur;} 
	return cur;
}
//输出迷宫
void print(){
   int i,j;
   for(i=0;i<10;i++)
   {for(j=0;j<10;j++)
		   printf("%c ",maze[i][j]);
   printf("\n");}
}
main(){
    SqStack S;
	SElemType e;
	int k;
	InitStack_Sq(S);
	SElemType curpos,start,end;
	printf("请输入起点位置:");
	scanf("%d%d",&start.x,&start.y);
	printf("请输入终点位置:");
	scanf("%d%d",&end.x,&end.y);
	printf("迷宫为:\n");
	print();
	curpos.x=start.x; 
	curpos.y=start.y;
	 
	do{
		if(Pass(curpos,k)){
		    maze[curpos.x][curpos.y]=(char)k;   //留下足迹(k为各个方向标的ASCII码)			
			Push_Sq(S,curpos);                    //加入路径
			if((curpos.x==end.x) && (curpos.y==end.y))  
			{maze[curpos.x][curpos.y]='*';
			 printf("路径为:\n");
			 print();return true; }  //到达终点
			 curpos=NextPos(curpos);      //当前位置的下一位置
		}
		else{
			if(S.top!=S.base){ 
				  maze[curpos.x][curpos.y]='@';
			      Pop_Sq(S,e);
				  curpos=e;
				  if(Pass(curpos,k)) maze[curpos.x][curpos.y]=(char)k;
				  curpos=NextPos(curpos);      //换下一方向搜索
			}				
		}
	}while(S.top!=S.base);	
	return false;
}