/*這個程序是學數據結構后寫的，里面涉及到了棧和隊列的一些操作。開始本來只是要做迷宮求解的，但就看著電腦在里面運行，沒有互動性也沒什么意思，于是加入了由人控制的角色，讓電腦控制的角色每走一步都計算一次當前兩者的最短距離去追趕人控制的角色。這個程序畫地圖的部分是得于網上的一個迷宮程序，漢字部分也是用的別別人寫好的子程序。其實這個程序還不是很完善，開始做好了一個，卻不知那兒弄丟了，假期因為參加電子設計大賽，都玩單片機去了，這方面的也忘差不多了，希望有興趣的朋友能改好了發給我.我的email:xiangyuan_122@163.com*/
/*本程序在TURBOC2.0下編譯通過,**.h文件可拷在INCLUDE文件夾下.*/
#include"stdio.h"
#include"graphics.h"
#include"conio.h"
#include"mprinthz.h"
#define N 10
#define P 4
unsigned *str1="貓捉老鼠！";
unsigned *str2="嘿嘿！看你往哪跑！";
/*定義迷宮數組*/
int maze[N][N]={
1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,1,1,1,0,1,
1,0,1,0,0,0,0,1,0,1,
1,0,1,0,1,1,0,1,0,1,
1,0,1,0,1,0,0,1,0,1,
1,0,1,0,0,0,0,1,0,1,
1,0,1,1,1,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};
int di[P]={0, 1, 0, -1 };
int dj[P]={1, 0, -1, 0 };
static int key;
static int step;
/*坐標結構*/
typedef struct
{
 int xpos;
 int ypos;
}postype;

/*隊列結點結構*/
typedef struct queuenode
{
 postype seat;/*當前坐標*/
 struct queuenode*next;/*指向后繼結點*/
 struct queuenode*pre;/*指向前驅結點*/
}queuenode,*link;


static link front=NULL;
static link rear=NULL;

/*棧結點結構*/
typedef struct stack_node
{
postype sdata;
struct stack_node*next;
}stack_list,*plink;

static plink path=NULL;

/*入棧操作*/
push(postype e)
{
plink new_node;
new_node=(plink)malloc(sizeof(stack_list));
if(!new_node)
{
printf("error:not enough memory!\n");
exit(0);
}
new_node->sdata.xpos=e.xpos;
new_node->sdata.ypos=e.ypos;
new_node->next=path;
path=new_node;
}

/*出棧操作*/
postype pop()
{
postype e;
plink top;
top=path;
if(path!=NULL)
{
e.xpos=path->sdata.xpos;
e.ypos=path->sdata.ypos;
path=path->next;
free(top);
return e;
}

}
 
/*建立隊列*/
void enqueue(postype value)
{
link newnode;
newnode=(link)malloc(sizeof(queuenode));
if(newnode==NULL)
{
printf("not enough memory!\n");
exit(0);
}
newnode->seat.xpos=value.xpos;
newnode->seat.ypos=value.ypos;
newnode->next=NULL;

if(rear==NULL)
 {  front=newnode;
    rear=newnode;
  newnode->pre=NULL;}
else
  {
  newnode->pre=front;
  rear->next=newnode;
  rear=newnode;
  }
}

/*刪除隊列結點*/
postype dequeue(void)
{
 postype e;
 front=front->next;
 e.xpos=front->seat.xpos;
 e.ypos=front->seat.ypos;

 return e;
}


postype nextpos(postype curpos,int v)
{
postype next_;
next_.xpos=curpos.xpos+di[v];
next_.ypos=curpos.ypos+dj[v];
return next_;
}

/*標準延時*/
void Delay(int clicks)
{
unsigned int far *clock=(unsigned int far *)0x0000046CL;
unsigned int now;
now=*clock;
while(abs(*clock-now)<clicks){}
}

/*畫地圖*/
void picture (int maze[][N])
{
int i,j;
setbkcolor(BLACK);
for(i=0;i<N;i++)
{for (j=0;j<N;j++)
 {if(maze[i][j]==1)
  {setfillstyle(1,LIGHTBLUE);
  bar(70+j*20,40+i*20,88+j*20,58+i*20);
  }
 else
  {setfillstyle(1,WHITE);
  bar(70+j*20,40+i*20,88+j*20,58+i*20);
  }
 } 
}
}

 

main(){
int visited[N+1][N+1];/*訪問標志數組*/
plink ptr;
link p,qp;
postype curpos;
postype next,out,imgcurman;
int found=0;
int i,j,curmanx,curmany;
init();
picture(maze);/*畫迷宮*/
printhz(200,10,str1,2);
curmanx=N-2;
curmany=N-2;/*設置逃跑者初始位置坐標*/
setfillstyle(1,YELLOW);
bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
curpos.xpos=1;
curpos.ypos=1;/*設置追趕者初始位置坐標*/

while(1)/*游戲循環*/
{
if(kbhit())/*檢測按鍵*/
{
key=bioskey(0);
/*按鍵處理*/ 
if(key==0x4800)/*UP方向鍵*/
{imgcurman.xpos=curmanx;
 imgcurman.ypos=curmany;/*復制逃跑者坐標*/
 if(maze[imgcurman.ypos-1][imgcurman.xpos]==0)/*當前位置上方為通道*/
  /*上行一步*/
  {setfillstyle(1,WHITE);
  bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
  curmany--;
  setfillstyle(1,YELLOW);
  bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20); 
  }                      
}
if(key==0x5000)/*DOWN方向鍵*/
{imgcurman.xpos=curmanx;
 imgcurman.ypos=curmany;/*復制逃跑者坐標*/
 if(maze[imgcurman.ypos+1][imgcurman.xpos]==0)/*當前位置下方為通道*/
 /*下行一步*/ 
 {setfillstyle(1,WHITE);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 curmany++;
 setfillstyle(1,YELLOW);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 }            
}

if(key==0x4b00)/*LEFT方向鍵*/
{imgcurman.xpos=curmanx;
 imgcurman.ypos=curmany;/*復制逃跑者坐標*/
 if(maze[imgcurman.ypos][imgcurman.xpos-1]==0)/*當前位置左方為通道*/
 /*左行一步*/
 {setfillstyle(1,WHITE);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 curmanx--;
 setfillstyle(1,YELLOW);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 }
}

if(key==0x4d00)/*RIGHT方向鍵*/
{imgcurman.xpos=curmanx;
 imgcurman.ypos=curmany;/*復制逃跑者坐標*/
 if(maze[imgcurman.ypos][imgcurman.xpos+1]==0)/*當前位置右方為通道*/ 
 /*右行一步*/
 {setfillstyle(1,WHITE);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 curmanx++;
 setfillstyle(1,YELLOW);
 bar(70+curmanx*20,40+curmany*20,88+curmanx*20,58+curmany*20);
 }
}
while(bioskey(1)) bioskey(0);/*清除鍵盤緩沖區*/
}

for(i=1;i<=N;i++)
   for(j=1;j<=N;j++)
  visited[i][j]=0;/*初始化訪問標志*/
  found=0;/*初始化追趕上標志*/
enqueue(curpos);/*追趕者當前坐標入隊列*/
visited[curpos.xpos][curpos.ypos]=1;/*當前訪問標志置1*/

while(!found)/*如沒有追上循環*/
 {
for(i=0;i<P;i++)
     {
next=nextpos(curpos,i);
if((maze[next.xpos][next.ypos]==0)&&(visited[next.xpos][next.ypos]==0))
         {visited[next.xpos][next.ypos]=1;
   if(next.xpos==curmanx&&next.ypos==curmany) found=1;
          enqueue(next);
         }
    }
curpos=dequeue();
}

  p=rear;
  step=2;
  while(p)
  {
  push(p->seat);
  p=p->pre;}
   while(rear){
   p=rear;
   rear=rear->next;
   free(p);}
   while(path&&step){
   out=pop();
   setfillstyle(1,GREEN);
   bar(70+out.xpos*20,40+out.ypos*20,88+out.xpos*20,58+out.ypos*20);
   Delay(2);
   setfillstyle(1,WHITE);
   bar(70+out.xpos*20,40+out.ypos*20,88+out.xpos*20,58+out.ypos*20);
   step--;}
   curpos.xpos=out.xpos;
   curpos.ypos=out.ypos;
   if(curpos.xpos==curmanx&&curpos.ypos==curmany) 
   {printhz(400,40,str2,1);
    Delay(35);
    printhz(400,40,str2,0);
    getch();break;}
   while(path){
   ptr=path;
   path=path->next;
   free(ptr);}

}

}