/**/ /*MazePath Demo BY Turbo C 2.0Copyright(c) RoverUnion. All right reserved.Filename: Maze.cAuthor Dongchengyu.Ver 1.10*/#include #include #include #include #include #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 10typedef 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 (m30 || n > 20) Error("Maze too large");
for (i = 0;i3) { y--; gotoxy(x, y); }
break;
case Down: if (y4) { x -= 2; gotoxy(x, y); }
break;
case Right: if (x 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();}网上找的，怎么用，你自己看看 |
