#include<stdio.h>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
#include<graphics.h>
#include<dos.h>
#define N 10
#define INIT_STACK_SIZE 20
#define STACKINCREMENT 10
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;
SqStack S;
/* maze array initialize */
int maze[N][N]={0,0,0,0,0,0,0,0,0,0,
0,1,0,0,1,1,1,0,1,0,
0,1,1,0,1,1,1,0,1,0,
0,1,1,1,1,0,0,1,1,0,
0,1,0,0,0,1,1,1,1,0,
0,1,1,1,0,1,1,1,1,0,
0,1,0,1,1,1,0,1,1,0,
0,1,0,0,0,1,0,0,1,0,
0,0,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0};
void InitGraph(void);
void Statement(void);
int Selection(int maze[N][N]);
void PrintMaze(int maze[N][N]);
SqStack InitStack(SqStack S);
SqStack FoundPath(SqStack S,int maze[N][N]);
SqStack Push(SqStack S,int path);
SqStack Pop(SqStack S,int *path);
int EmptyStack(SqStack S);
int main(void)
{
int path,*temp;
/* clear screen function */
clrscr();
/* graph function library initialize */
InitGraph();
/* author statement function,and clear author statement*/
Statement();
/* selection fixed maze or random maze */
maze[N][N]=Selection(maze);
/* print original maze array function */
PrintMaze(maze);
/* initialize stack function */
S=InitStack(S);
/* search maze path function */
S=FoundPath(S,maze);
/* print maze path function,color is white */
textcolor(15);
if(!EmptyStack(S))
{
for(temp=S.base;temp<=S.top-1;temp++)
{
sleep(1);
cprintf("%d->",*temp);
}
cprintf("success\n\n\r");
while(!kbhit())
{
textcolor(YELLOW);
cprintf("Congratulation You Pass!,Press any key exit program!\r");
delay(100000);
cprintf(" \r");
delay(100000);
}
}
/* free dynamic malloc memory and success exit program,
and close graph library*/
getch();
free(S.base);
return 0;
}
void InitGraph(void)
{
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,"");
}
void Statement(void)
{
setfillstyle(1,3);
bar(0,0,640,480);
setfillstyle(1,BLUE);
bar(100,100,540,380);
setcolor(LIGHTRED);
settextstyle(1,0,2);;
outtextxy(200,130,"This is maze program!");
setcolor(WHITE);
settextstyle(1,0,1);
outtextxy(220,180,"Author: -TianXiaWuDi");
setcolor(LIGHTGREEN);
settextstyle(0,0,0);
outtextxy(300,230,"MSN: tianxiawudi@hotmail.com");
outtextxy(300,250,"Email: tianxiawudi@163.com");
outtextxy(300,270,"QQ: 425697422");
outtextxy(380,290,"-wudi");
outtextxy(380,310,"2006.4.9");
outtextxy(180,330,"Please press anykey into program.");
outtextxy(150,360,"CopyRight by TianXiaWuDi.All right reserved.");
getch();
cleardevice();
closegraph();
}
int Selection(int maze[N][N])
{
int choice,i,j;
srand(time(NULL));
textcolor(15);
cprintf("Please input your choice,'1' is fixed maze,'2' is random maze,else exit program:");
scanf("%d",&choice);
printf("\n\r");
if(choice==1)
{
cprintf("You enter %d,so you choice fixed maze.\n\n\r",choice);
return maze[N][N];
}
else if(choice==2)
{
/* random produce 0 or 1 */
cprintf("You enter %d,so you choice random maze.\n\n\r",choice);
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
maze[i][j]=rand()%2;
}
maze[1][1]=1;
maze[8][8]=1;
return maze[N][N];
}
else
exit(0);
}
void PrintMaze(int maze[N][N])
{
int i,j;
/* set output text color */
textcolor(2);
for(i=0;i<=N-1;i++)
{
printf("\t");
for(j=0;j<=N-1;j++)
{
cprintf("%d ",maze[i][j]);
}
printf("\n\r");
}
printf("\n\n\r");
}
SqStack InitStack(SqStack S)
{
/* give stack base address malloc memory space */
if((S.base=(int *)malloc(INIT_STACK_SIZE * sizeof(int)))==NULL)
{
exit(1);
}
/* stack top pointer point to stack base address */
S.top=S.base;
S.stacksize=INIT_STACK_SIZE;
return S;
}
SqStack FoundPath(SqStack S,int maze[N][N])
{
int i=1,j=1,path;
/* setting maze export value */
maze[N-2][N-2]=88;
while(maze[i][j]!=maze[N-2][N-2])
{
/* maze[1][1] is maze entrance */
if(maze[i][j]==1)
{
/* get path value,and push path value into stack,
and set current path value is 0,and continue toward east */
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0)
{
/* east is can not go,toward south */
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
i++;
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0)
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
j--;
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0)
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
i--;
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else
{
if(!EmptyStack(S))
{
S=Pop(S,&path);
i=path/10;
j=path%10;
}
else
{
textcolor(LIGHTRED);
while(!kbhit())
{
cprintf("Sorry! The maze has no pass path,press any key exit program!\r");
delay(100000);
cprintf(" \r");
delay(100000);
}
exit(1);
}
}
}/* else */
}/* else */
}/* else */
}/* while */
/* put the last path value push stack */
if(maze[i][j]==maze[N-2][N-2])
{
path=10*i+j;
S=Push(S,path);
}
/* return get path of stack variable */
return S;
}
/* judgment stack empty function;if stack empty return 1;
if stack is not empty,return 0; */
int EmptyStack(SqStack S)
{
int flag=0;
if(S.top==S.base)
flag=1;
return flag;
}
/* put get path value push stack */
SqStack Push(SqStack S,int path)
{
*(S.top++)=path;
if(S.top-S.base >= S.stacksize)
{
if((S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(int)))==NULL)
{
exit(1);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
return S;
}
/* pop stack function*/
SqStack Pop(SqStack S,int *path)
{
if(!EmptyStack(S))
*path=*(--S.top);
return S;
}
