程序目的：输入一个任意大小的迷宫，用栈求出一条走出迷宫的路径，并显示在屏幕上。程序实现：可以实现载入迷宫和保存迷宫，附带文件中有4个测试迷宫路径的文件test1~4.dd。请将这些文件拷贝到TC当前目录下，或者在载入时写明完全路径。由于屏幕大小的限制，当用户自己输入迷宫时一定要注意：迷宫大小是有限制的，不小于4*3,不大于30*20。否则会出现错误信息。输入开始时全是墙，用上下左右键移动，用Del键删除墙，形成通路，用Enter键添加墙。输入结束时可以将迷宫保存下来，以dd为扩展名。输入完毕时用F9键来得到结果，找到路径时，屏幕下方会出现Path found，否则出现Path not found。程序经Turbo C 2.0编译调试成功。运行时不用添加任何运行库。不可以在VC上编译。下载DOS版和windows版的迷宫游戏全部代码用户名：migong ---------------------------------------------------------------------------------- /* MazePath Demo BY Turbo C 2.0 Copyright(c) RoverUnion. All right reserved. Filename: Maze.c Author Dongchengyu. Ver 1.10 */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <conio.h> #include <dos.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define F9 0x43 #define Esc 0x1b #define Del 0x53 #define Home 0x47 #define End 0x4f #define Space 0x20 #define Up 0x48 #define Down 0x50 #define Left 0x4b #define Right 0x4d #define Enter 0x0d #define F2 0x3c #define F3 0x3d #define STACK_INIT_SIZE 200 #define STACKINCREMENT 10 typedef int Boolean; typedef int Status; typedef struct { int x; int y; } PosType; typedef struct { int ord; PosType seat; int di; } SElemType; typedef struct { int td; int foot; int mark; } MazeType; typedef struct { SElemType *base; SElemType *top; int stacksize; } Stack; int Maze[20][30]; MazeType maze[20][30]; PosType StartPlace; PosType EndPlace; int count; int m,n; Boolean b_start=FALSE,b_end=FALSE; void CreatMaze(void); Status SaveMaze(char *filename); Status LoadMaze(char *filename); void Error(char *message); Status InitStack(Stack *s); Status DestroyStack(Stack *s); Status ClearStack(Stack *s); Boolean StackEmpty(Stack *s); int StackLength(Stack *s); Status Push(Stack *s,SElemType e); SElemType Pop(Stack *s,SElemType e); Status GetTop(Stack *s,SElemType *e); Status StackTraverse(Stack *s,Status (* visit)(SElemType *se)); Boolean Pass(PosType curpos); void MarkPrint(PosType seat); void FootPrint(PosType curpos); PosType NextPos(PosType seat,int di); Status MazePath(PosType start,PosType end); void CreatMaze(void) /* Form the maze. */ { void Error(char *message); Status SaveMaze(char *filename); Status LoadMaze(char *filename); int i,j; int x,y; char c; char savename[12],loadname[12]; Boolean flag=FALSE,load=FALSE; clrscr(); printf("Menu:\n\n"); printf("1.Load Mazefile*.dd)\n\n"); printf("2.Input Maze:\n\n"); printf("Input your choice: "); do { c=getch(); switch(c) { case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''); break; case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': putch(''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''); break; case Esc: sleep(1); exit(1); default: break; } } while(c!=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''&&c!=''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''') ; if(c==''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''') { printf("\n\nLoadName: "); scanf("%s",loadname); if(LoadMaze(loadname)) { sleep(1); load=TRUE; } else { gotoxy(1,9); printf("Load fail! "); } } if(!load) { printf("\nInput the maze''''''''''''''''''''''''''''''''s size:\n"); printf("\nInput Length :\n"); scanf("%d",&m); printf("\nInput Width :\n"); scanf("%d",&n); if(m<4||n<4) Error("Input"); if(m>30||n>20) Error("Maze too large"); for(i=0;i<30;i++) for(j=0;j<20;j++) Maze[j]=2; StartPlace.x=0; StartPlace.y=0; EndPlace.x=0; EndPlace.y=0; clrscr(); printf("\n"); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf(" #"); Maze[i-1][j-1]=0; } printf("\n"); } } gotoxy(65,5); printf("''''''''''''''''''''''''''''''''#'''''''''''''''''''''''''''''''':Wall"); gotoxy(65,7); printf("Start:Home"); gotoxy(65,9); printf("End:End"); gotoxy(65,11); printf("Delete Wallel"); gotoxy(65,13); printf("Enter Wall:Enter"); gotoxy(65,15); printf("Save Maze:F2"); gotoxy(65,17); printf("Complete:F9"); gotoxy(65,19); printf("Exit:Esc"); gotoxy(4,3); x=4;y=3; do { c=getch(); switch(c) { case Up: if(y>3) { y--; gotoxy(x,y); } break; case Down: if(y<n) { y++; gotoxy(x,y); } break; case Left: if(x>4) { x-=2; gotoxy(x,y); } break; case Right: if(x<2*m-2) { x+=2; gotoxy(x,y); } break; case Del: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) b_start=FALSE; if(y-2==EndPlace.y&&x/2-1==EndPlace.x) b_end=FALSE; putch('''''''''''''''''''''''''''''''' ''''''''''''''''''''''''''''''''); Maze[y-2][x/2-1]=1; gotoxy(x,y); break; case Enter: if(y-2==StartPlace.y&&x/2-1==StartPlace.x) break; if(y-2==EndPlace.y&&x/2-1==EndPlace.x) break; putch(''''''''''''''''''''''''''''''''#''''''''''''''''''''''''''''''''); Maze[y-2][x/2-1]=0; gotoxy(x,y); break; case Home: if(Maze[y-2][x/2-1]&&!b_start) { StartPlace.x=x/2-1; StartPlace.y=y-2; putch(''''''''''''''''''''''''''''''''S''''''''''''''''''''''''''''''''); gotoxy(x,y); b_start=TRUE; } break; case End: if(Maze[y-2][x/2-1]&&!b_end) { EndPlace.x=x/2-1; EndPlace.y=y-2; putch(''''''''''''''''''''''''''''''''E''''''''''''''''''''''''''''''''); gotoxy(x,y); b_end=TRUE; } break; case Esc: gotoxy(2,22); printf("exit"); sleep(1); exit(1); case F9: if(b_start&&b_end) flag=TRUE; break; case F2: gotoxy(2,22); printf("Savename:"); scanf("%s",savename); gotoxy(2,22); if(SaveMaze(savename)) printf("Save OK! "); else printf("Save fail! "); sleep(1); gotoxy(2,22); printf(" "); gotoxy(x,y); break; default: break; } } while(!flag); for(i=0;i<30;i++) for(j=0;j<20;j++) { maze[j].td=Maze[j]; maze[j].mark=0; maze[j].foot=0; } } Status LoadMaze(char *file) /* The maze has been loaded. */ { FILE *fp; char *buffer; char ch; int i=0,j,k; Boolean len=FALSE,wid=FALSE; if((fp=fopen(file,"r"))==NULL) return ERROR; buffer=(char *)malloc(600*sizeof(char)); ch=fgetc(fp); while(ch!=EOF) { buffer=ch; i++; ch=fgetc(fp); } m=30;n=20; for(i=0;i<600;i++) { j=i/30; k=i%30; if(buffer==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!len){ m=i; len=TRUE; } if(k==0&&buffer==''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''&&!wid){ n=j; wid=TRUE; } switch(buffer) { case ''''''''''''''''''''''''''''''''0'''''''''''''''''''''''''''''''': Maze[j][k]=0; break; case ''''''''''''''''''''''''''''''''1'''''''''''''''''''''''''''''''': Maze[j][k]=1; break; case ''''''''''''''''''''''''''''''''2'''''''''''''''''''''''''''''''': Maze[j][k]=2; break; case ''''''''''''''''''''''''''''''''3'''''''''''''''''''''''''''''''': Maze[j][k]=1; StartPlace.x=k; StartPlace.y=j; b_start=TRUE; break; case ''''''''''''''''''''''''''''''''4'''''''''''''''''''''''''''''''': Maze[j][k]=1; EndPlace.x=k; EndPlace.y=j; b_end=TRUE; break; default : break; } } fclose(fp); clrscr(); for(i=0;i<30;i++) for(j=0;j<20;j++) { maze[j].td=Maze[j]; maze[j].foot=0; maze[j].mark=0; if(Maze[j]==0) { gotoxy(2*i+2,j+2); putch(''''''''''''''''''''''''''''''''#''''''''''''''''''''''''''''''''); } } gotoxy(2*StartPlace.x+2,StartPlace.y+2); putch(''''''''''''''''''''''''''''''''S''''''''''''''''''''''''''''''''); gotoxy(2*EndPlace.x+2,EndPlace.y+2); putch(''''''''''''''''''''''''''''''''E''''''''''''''''''''''''''''''''); return OK; } Status SaveMaze(char *filename) /* The maze has been saved. */ { FILE *fp; char *buffer; int i,j,k; fp=fopen(filename,"wb"); buffer=(char *)malloc(600*sizeof(char)); for(i=0;i<600;i++) { j=i/30; k=i%30; switch(Maze[j][k]) { case 0: buffer=''''''''''''''''''''''''''''''''0''''''''''''''''''''''''''''''''; break; case 1: buffer=''''''''''''''''''''''''''''''''1''''''''''''''''''''''''''''''''; break; case 2: buffer=''''''''''''''''''''''''''''''''2''''''''''''''''''''''''''''''''; break; default : Error("Write"); break; } if(k==StartPlace.x&&j==StartPlace.y) buffer=''''''''''''''''''''''''''''''''3''''''''''''''''''''''''''''''''; if(k==EndPlace.x&&j==EndPlace.y) buffer=''''''''''''''''''''''''''''''''4''''''''''''''''''''''''''''''''; } fwrite(buffer,600,1,fp); free(buffer); fclose(fp); return OK; } void Error(char *message) { clrscr(); fprintf(stderr,"Error:%s\n",message); exit(1); } /* Error */ Status InitStack(Stack *s) /* The stack s has been created and is initialized to be empty. */ { s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s->base) Error("Overflow"); s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } /* InitStack */ Status DestroyStack(Stack *s) /* The stack s has been destroyed. */ { s->top=NULL; s->stacksize=0; free(s->base); s->base=NULL; return OK; } /* DestroyStack */ Status ClearStack(Stack *s) /* The stack has been clear to be maximum. */ { s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } /* ClearStack */ Boolean StackEmpty(Stack *s) /* Check if the stack s is empty. */ { if(s->top==s->base) return TRUE; else return FALSE; } /* StackEmpty */ int StackLength(Stack *s) /* Gain the length of the stack s. */ { if(s->top>s->base) return (int)(s->top-s->base); else return 0; } /* StackLength */ Status Push(Stack *s,SElemType e) /* The element e has been pushed into the stack s. */ { if(s->top-s->base>=s->stacksize) { s->base=(SElemType *)realloc(s->base, (s->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s->base) Error("Overflow"); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; return OK; } /* Push */ SElemType Pop(Stack *s,SElemType e) /* The element e has been removed from the stack s. */ { if(s->top==s->base) Error("Pop"); e=*--s->top; return e; } /* Pop */ Status GetTop(Stack *s,SElemType *e) /* The element e has got to the top of the stack s.*/ { if(s->top==s->base) Error("GetTop"); *e=*(s->top-1); return OK; } /* GetTop */ /* Traverse the stack s using ''''''''''''''''''''''''''''''''visiting'''''''''''''''''''''''''''''''' function. */ /* Status StackTraverse(Stack *s,Status (* visit)(SElemType *se)) { SElemType p; int result; if(s->top==s->base) return ERROR; p=s->base; while(!(p==s->top)) { result=(*visit)(p); p++; } return OK; } */ Boolean Pass(PosType curpos) /* Check if the current position can be passed. */ { if(maze[curpos.x][curpos.y].td==1&& maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0) return TRUE; else return FALSE; } /* Pass */ void MarkPrint(PosType seat) /* Mark the position seat. */ { maze[seat.x][seat.y].mark=-1; /* Marking ''''''''''''''''''''''''''''''''-1'''''''''''''''''''''''''''''''' symbolize the current position cannot be put. */ } /* MarkPrint */ void FootPrint(PosType curpos) /* The foot of the curpos of the maze has been set ''''''''''''''''''''''''''''''''true''''''''''''''''''''''''''''''''. */ { maze[curpos.x][curpos.y].foot=1; } /* FootPrint */ PosType NextPos(PosType seat,int di) { switch(di) { case 1: seat.y++; return seat; /* Eastward */ case 2: seat.x++; return seat; /* Southward */ case 3: seat.y--; return seat; /* Westward */ case 4: seat.x--; return seat; /* Northward */ default: seat.x=0; seat.y=0; return seat; } } /* NextPos */ /* The key to the program. */ /* Pre: The maze array & the startplace & the endplace. Post: Find the one traverse of the maze and perform the mazepath. Uses: The ADT stack class. */ Status MazePath(PosType start,PosType end) { PosType curpos; int curstep; SElemType e; Stack *s,stack; stack.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!stack.base) Error("Overflow"); stack.top=stack.base; stack.stacksize=STACK_INIT_SIZE; s=&stack; curpos=start; curstep=1; do { if(Pass(curpos)) { FootPrint(curpos); e.ord=curstep; e.seat=curpos; e.di=1; gotoxy((curpos.y+1)*2,curpos.x+2); putch(''''''''''''''''''''''''''''''''@''''''''''''''''''''''''''''''''); delay(8000); /* pospone time. */ Push(s,e); if(curpos.x==end.x&&curpos.y==end.y) /* Proceed recursively. */ { DestroyStack(s); return TRUE; } curpos=NextPos(curpos,1); /* Try next position. */ curstep++; } else { if(!StackEmpty(s)) { e=Pop(s,e); /* Removed e from s. */ while(e.di==4&&!StackEmpty(s)) /* Four directions have been checked and s is not empty. */ { MarkPrint(e.seat); gotoxy((e.seat.y+1)*2,e.seat.x+2); putch(''''''''''''''''''''''''''''''''@''''''''''''''''''''''''''''''''); delay(8000); /* Pospone time. */ gotoxy((e.seat.y+1)*2,e.seat.x+2); putch('''''''''''''''''''''''''''''''' ''''''''''''''''''''''''''''''''); e=Pop(s,e); /* Remove e from s. */ curstep--; } if(e.di<4) /* The current position hasnot been checked. */ { e.di++; Push(s,e); /* Insert e into s. */ curpos=NextPos(e.seat,e.di); /* Try next position. */ } } } } while(!StackEmpty(s)); DestroyStack(s); return FALSE; } /* MazePath */ void main() { PosType start,end; CreatMaze(); start.x=StartPlace.y; start.y=StartPlace.x; end.x=EndPlace.y; end.y=EndPlace.x; if(MazePath(start,end)) { gotoxy(2,22); printf("Path found\n"); } else { gotoxy(2,22); printf("Path not found\n"); } getch(); clrscr(); }