C语言程序设计:用栈实现的迷宫寻径演示

#include <stdio.h> 
#include <stdlib.h> 
#include <graphics.h> 
#include <conio.h> 
#include <dos.h> 

#define COL 20 
#define ROW 20 
#define LEFT 120 
#define TOP 40 
#define RIGHT 520 
#define BOTTOM 440 
#define SMALL 20 

int Maze[COL][ROW]={ 
   {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 
   {1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1}, 
   {1,0,1,0,0,1,0,0,1,0,1,0,1,1,0,1,0,0,0,1}, 
   {1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1}, 
   {1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1}, 
   {1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0,0,1,0,1}, 
   {1,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1}, 
   {1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1}, 
   {1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1}, 
   {1,0,1,0,0,1,1,0,0,1,0,0,1,1,0,0,1,0,1,1}, 
   {1,0,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,0,0,1}, 
   {1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,0,1,1,0,1}, 
   {1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1}, 
   {1,1,0,1,1,0,1,0,0,1,0,1,1,1,0,1,1,0,1,1}, 
   {1,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1}, 
   {1,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1}, 
   {1,0,1,0,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1}, 
   {1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,1,1}, 
   {1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,0,0,1}, 
   {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}; 
int flag=1; 
typedef struct Seat 
{ 
    int x,y; 
    int dir; 
}Seat; 

typedef struct LSNode 
{ 
    Seat data; 
    struct LSNode* next; 
}LSNode,*SNode; 

typedef struct LSk  
{ 
    SNode top; 
}LSk,*LStack; 

void InitLStack(LStack LS) 
{ 
    if(LS==NULL) 
    { 
        LS=(LStack)malloc(sizeof(LSk)); 
    } 
    LS->top=NULL; 
} 

Seat* Peek(LStack LS) 
{ 
    Seat* p; 
    Seat temp; 
    temp=LS->top->data; 
    p=(Seat*)malloc(sizeof(Seat)); 
    p->dir=temp.x; 
    p->x=temp.x; 
    p->y=temp.y; 
    return p; 
} 

void Push(LStack LS,Seat value) 
{ 
    SNode p; 
    p=(SNode)malloc(sizeof(LSNode)); 
    p->data.x=value.x; 
    p->data.y=value.y; 
    p->data.dir=value.dir; 
    p->next=LS->top; 
    LS->top=p; 
} 

Seat* Pop(LStack LS) 
{ 
    SNode p; 
    Seat *res; 
    Seat temp; 
    res=(Seat*)malloc(sizeof(Seat)); 
    res->x=-1; 
    res->y=-1; 
    res->dir=0; 
    p=LS->top; 
    if(p==NULL) 
    { 
        flag=0; 
        return res; 
    } 
    temp=p->data; 
    res->x=temp.x; 
    res->y=temp.y; 
    res->dir=temp.dir; 
 LS->top=p->next; 
    return res; 
} 

int IsEmpty(LStack LS) 
{ 
    if(LS->top==NULL) 
        return 1; 
    else  
        return 0; 
} 

void Print(LStack LS) 
{ 
    SNode p; 
    if(LS->top==NULL) 
    { 
        printf("No path\n"); 
        return; 
    } 
    p=LS->top; 
    printf("Path is as follow:\n"); 
    while(p!=NULL) 
    { 
        printf("%d,%d\t",p->data.x,p->data.y); 
  p=p->next;    
    } 
    printf("\n"); 
} 

void drawcake(int x,int y) 
{ 
    setfillstyle(SOLID_FILL,BLUE); 
    bar(LEFT+1+x*SMALL,TOP+1+y*SMALL,RIGHT-1-19*SMALL+x*SMALL,BOTTOM-1-19*SMALL+y*SMALL); 
} 

void draw(int x,int y) 
{ 
    setfillstyle(SOLID_FILL,RED); 
    bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL); 
} 

void undraw(int x,int y) 
{ 
    setfillstyle(SOLID_FILL,BLACK);     bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL); 
} 

void footprint(int x,int y) 
{ 
    setfillstyle(SOLID_FILL,GREEN); 
    bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL); 
} 

void Tranverse(Seat start,Seat end,LStack LS) 
{ 
     
    Seat cur; 
    Seat *top; 
    start.dir=1; 
    Push(LS,start); 
    top=Peek(LS); 
    while(!IsEmpty(LS)&&(top->x!=end.x||top->y!=end.y)) 
    { 
        top=Pop(LS); 
        cur.x=top->x; 
        cur.y=top->y; 
        cur.dir=top->dir; 
 /*     printf("%d,%d,%d\t",cur.x,cur.y,cur.dir);     */ 

        if(cur.dir==5) 
        { 
            Maze[cur.x][cur.y]=0; 
            footprint(cur.y,cur.x); 
            continue; 
        } 
        else 
        { 
            switch(cur.dir) 
            { 
            case 1: 
                if(cur.y+1<COL) 
                { 

                    if(Maze[cur.x][cur.y+1]==0) 
                    { 
                        Maze[cur.x][cur.y+1]=2; 
                        cur.dir=2; 
                        Push(LS,cur); 
                        cur.dir=1; 
                        cur.y+=1; 
                        Push(LS,cur); 
                        draw(cur.y,cur.x); 
                        break; 
                    } 
                } 
                cur.dir=2; 
                Push(LS,cur); 
                break; 
            case 2: 
                if(cur.x+1<ROW) 
                { 
                    if(Maze[cur.x+1][cur.y]==0) 
                    { 
                        Maze[cur.x+1][cur.y]=2; 
                        cur.dir=3; 
                        Push(LS,cur); 
                        cur.dir=1; 
                        cur.x+=1; 
                        Push(LS,cur); 
                        draw(cur.y,cur.x); 
                        break; 
                    } 
                } 
                cur.dir=3; 
                Push(LS,cur); 
                break; 
            case 3: 
                if(cur.y-1>=0) 
                { 
      
                    if(Maze[cur.x][cur.y-1]==0) 
                    { 
                        Maze[cur.x][cur.y-1]=2; 
                        cur.dir=4; 
                        Push(LS,cur); 
                        cur.dir=1; 
                        cur.y-=1; 
                        Push(LS,cur); 
                        draw(cur.y,cur.x); 
                        break; 
                    } 
                } 
                cur.dir=4; 
                Push(LS,cur); 
                break; 
            case 4: 
                if(cur.x-1>=0) 
                { 
                    if(Maze[cur.x-1][cur.y]==0) 
                    { 
                        Maze[cur.x-1][cur.y]=2; 
                        cur.dir=5; 
                        Push(LS,cur); 
                        cur.dir=1; 
                        cur.x-=1; 
                        Push(LS,cur); 
                        draw(cur.y,cur.x); 
                        break; 
                    } 
      
                }                 cur.dir=5; 
                Push(LS,cur); 
                break; 
            } 
        } 
        top=Peek(LS); 
        delay(20000); 
    } 
/*  printf("\nTransver finished\n");*/ 
    getch(); 
} 

void Human() 
{ 
    char ch; 
    int x=1,y=1; 
    do{ 
        ch=bioskey(0); 
        switch(ch) 
        { 
            case 19200:   /*°'?ò×ó?ü*/ 
            if(Maze[y][x-1]==0) 
            { 
                undraw(x,y); 
                Maze[y][x]=0; 
                x--; 
                draw(x,y); 
                Maze[y][x]=2; 

            } 
            break; 
            case 19712:   /*°'?òóò?ü*/ 
                if(Maze[y][x+1]==0) 
                { 
                    undraw(x,y); 
                    Maze[y][x]=0; 
                    x++; 
                    draw(x,y); 
                    Maze[y][x]=2; 

                } 
                break; 
            case 18432:   /*°'?òé??ü*/ 
                if(Maze[y-1][x]==0) 
                { 
                    undraw(x,y); 
                    Maze[y][x]=0; 
                    y--; 
                    draw(x,y); 
                    Maze[y][x]=2; 

                } 
                break; 
            case 20480:   /*°'?ò???ü*/ 
                if(Maze[y+1][x]==0) 
                { 
                    undraw(x,y); 
                    Maze[y][x]=0; 
                    y++; 
                    draw(x,y); 
                    Maze[y][x]=2; 

                } 
                break; 
            } 
            if(Maze[18][18]==2)ch=283; 
    }while(ch!=283); 
    if(Maze[18][18]==2)printf("                          You are successed !"); 
    getch(); 
} 

int main() 
{ 
    LStack ls; 
    Seat st; 
    Seat en; 
    int gr=DETECT,gm,i,j,x=1,y=1,ch; 
    float f; 
    st.x=1;    st.y=1;    st.dir=1; 
    en.x=18;en.y=18;en.dir=1; 
    ls=(LStack)malloc(sizeof(LSk)); 
    InitLStack(ls); 

    initgraph(&gr,&gm,""); 
    cleardevice(); 
    setbkcolor(0); 
    for(i=0;i<20;i++) 
        for(j=0;j<20;j++) 
            if(Maze[i][j]==1)drawcake(j,i); 
    draw(x,y); 

    printf("Tranverse start:\n"); 
    Tranverse(st,en,ls); 
/*    printf("The result as follow:\n"); 
    Print(ls);  */ 
    getch(); 
    return 0; 
}