迷宫找出路程序

/*========================================================== ==
  钻迷宫<2.0>
  迷宫用二维数组存储;
  迷宫随机生成;
  前进方向只有四个,就是上下左右;
  用栈存储走过的路,碰壁可以返回;
  TC2.0下编译通过!
  作者:yuleol E_mail:kuworm@126.com
  更新了迷宫显示方式,使屏幕不再闪烁!
============================================================ */
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define UP 1   /*用于存储方向的常量*/
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define OK 0
#define ERROR -1

struct  maze{
 int left;
 int top;
 int right;
 int bottom;
 int sign; /*记号(0表示空白,1表示墙,2表示走过的路,3表示走过并且返回的路,4老鼠所在位置)*/
}lab[22][42];/*定义迷宫存储结构*/

typedef struct SNode{
 int data;
 struct SNode *next;
}SNode;

typedef struct {
 int length;
 SNode *top;
}STACK;/*定义存储走过路线的栈*/

/*栈初始化*/
void InitStack(STACK *S)
{
 S->top=NULL;
 S->length=NULL;
}

/*元素e入栈*/
int Push(STACK *S,int e)
{
 SNode *p;
 p=(SNode *)malloc(sizeof(SNode));
 if(!p) return ERROR;
 p->data=e;
 p->next=S->top;
 S->top=p;
 S->length++;
 return OK;
}

/*栈顶元素出栈,e带回栈顶元数*/
int Pop(STACK *S,int *e)
{
 SNode *p;
 if(S->top==NULL) return ERROR;
 p=S->top;
 *e=p->data;
 S->top=p->next;
 S->length–;
 free(p);
 return OK;
}
/*判断S是否为空栈*/
int Empty(STACK S)
{
 if(S.top==NULL) return OK;
 return ERROR;
}

/*初始化图形显示*/
int initialize(void)
{
    int gdriver, gmode,errorcode;
    gdriver=VGA;
    gmode=VGAHI;
    initgraph(&gdriver, &gmode, “d:\c源码”);
    errorcode = graphresult();
    if (errorcode != grOk)  /* an error occurred */
   {
      printf(“Graphics error: %s\n”, grapherrormsg(errorcode));
      printf(“Press any key to halt:”);
      getch();
      exit(1);             /* return with error code */
   }
   return 0;
}

void showmaze(int i,int j)
{/*显示迷宫函数*/
  switch(lab[j].sign)
  {
   case 0: setfillstyle(SOLID_FILL,LIGHTBLUE);break;
   case 1: setfillstyle(SOLID_FILL,MAGENTA); break;
   case 2: setfillstyle(SOLID_FILL,GREEN);break;
   case 3: setfillstyle(SOLID_FILL,DARKGRAY);break;
   case 4: setfillstyle(SOLID_FILL,BLUE);break;
  }
  bar(lab[j].left,lab[j].top,lab[j].right,lab[j].bottom);
}

/*生成迷宫函数*/
void initialmaze()
{
 int i,j,n,leftx=100,topy=50,rightx=110,bottomy=60;
 srand((int)time(0));
 for(i=0;i<22;i++)/*随机成生迷宫*/
  for(j=0;j<42;j++)
  {
   lab[j].left=leftx+j*10;
   lab[j].top=topy+i*10;
   lab[j].right=rightx+j*10;
   lab[j].bottom=bottomy+i*10;
   n=rand()%20;
   if(n<5)
   lab[j].sign=1;
   else
   lab[j].sign=0;  
  }
 for(i=0;i<42;i++)/*成生迷宫四周*/
 {
  lab[0].sign=1;
  lab[21].sign=1;
 }
 for(i=0;i<22;i++)/*成生迷宫四周*/
 {
  lab[0].sign=1;
  lab[41].sign=1;
 }
 lab[1][0].sign=0;/*为迷宫留入口及出口*/
 lab[1][1].sign=0;
 lab[1][2].sign=0;
 lab[20][41].sign=0;
 lab[20][40].sign=0;
 lab[20][39].sign=0;
 for(i=0;i<22;i++)/*随机成生迷宫*/
  for(j=0;j<42;j++)
    showmaze(i,j);
}

int main(void)
{
 int i,j,way;
 char flag=’0′;
 STACK S;/*定义一个用于存储老鼠走过的路线的栈*/
 initialize();/*初始化图形显示*/
 InitStack(&S);/*初始化栈*/
 setbkcolor(LIGHTBLUE);/*设置背景色*/
    setcolor(MAGENTA);/*设置前景色*/
 initialmaze();/*成生迷宫*/
 i=1;/*初始化老鼠位置*/
 j=0;
 lab[j].sign=4;
 showmaze(i,j);/*显示迷宫*/
 setfillstyle(SOLID_FILL,BLUE);
 bar(120,300, 480, 350);
 moveto(130,310);
 outtext(“1.QUICK    2.SLOW”);
 moveto(130,330);
 outtext(“Chooses 1 or 2″);
 while(flag!=’1′ && flag!=’2′) flag=getche();
 bar(120,300, 480, 350);
 moveto(130,320);
 if(flag==’2′)
 outtext(“You Chooses 2.SLOW”);
 do{
  lab[j].sign=2;
  showmaze(i,j);
  if(lab[j+1].sign==0)/*RIGHT*/
  {
   j++;
   Push(&S,RIGHT);
  }
  else if(lab[i+1][j].sign==0)/*DOWN*/
  {
   i++;
   Push(&S,DOWN);
  } 
  else if(lab[j-1].sign==0)/*LEFT*/
  {
   j–;
   Push(&S,LEFT);
  }
  else if(lab[i-1][j].sign==0)/*UP*/
  {
   i–;
   Push(&S,UP);
  }
  else /*没路*/
  {
   if(Empty(S)==OK) /*已经退回起点*/
   {
    setfillstyle(SOLID_FILL,BLUE);
    bar(120,300, 480, 350);
    moveto(130,310);
    outtext(“The labyrinth does not have the outlet!”);
    moveto(130,330);
    outtext(“Press any key to exit…”);
    getche();
    exit(1);
   }
   else/*返回一步*/
   {
    Pop(&S,&way);
    lab[j].sign=3;
    showmaze(i,j);
    switch(way)
    {
     case RIGHT:j–;break;
     case DOWN:i–;break;
     case LEFT:j++;break;
     case UP:i++;break;
    }
   }
  }
  lab[j].sign=4;
  showmaze(i,j);/*显示迷宫*/
  if(flag==’2′)
  {
   delay(90000);
   sound(700); 
      delay(10000); 
      nosound();
  }
 }while(i!=20 || j!=41);/*走到出口*/
 setfillstyle(SOLID_FILL,BLUE);
 bar(120,300, 480, 350);
 moveto(130,310);
 outtext(“Found a road!”);
 moveto(130,330);
 outtext(“Press any key to exit…”);
    getche();
    closegraph();/*关闭图形显示*/
    return 0;
}