maze.c

Huffman和迷宫问题Huffman和迷宫问题Huffman和迷宫问题Huffman和迷宫问题

#include<stdio.h>
#include<conio.h>
#define stack_init_size 100
#define increment 10
int maze[10][10]={
1,1,1,1,1,1,1,1,1,1,
0,0,0,1,1,1,1,1,0,1,
1,1,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,0,0,0,1,
1,0,1,1,1,1,1,1,0,1,
1,0,0,0,1,0,0,0,0,0,
1,0,1,0,0,0,1,1,0,1,
1,0,1,1,1,0,1,1,0,1,
1,1,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,};

typedef struct{
    int x;
    int y;
}PosType;

typedef struct{
    int ord;
    PosType seat;
    int di;
}SElemType;

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

int equal(PosType a,PosType b)
{
    if(a.x==b.x&&a.y==b.y)
        return 1;
    else
        return 0;
}
void set(PosType *a,int x,int y)
{
    (*a).x=x;
    (*a).y=y;
}

int InitStack(SqStack *s)
{
    (*s).base=(SElemType *)malloc(stack_init_size*sizeof(SElemType));
    if(!(*s).base)
        exit(0);
    (*s).top=(*s).base;
    (*s).stacksize=stack_init_size;
    return 1;
}

int GetTop(SqStack s,SElemType *e)
{
    if(s.top==s.base)
        return 0;
    (*e)=*(s.top-1);
    return 1;
}

int Push(SqStack *s,SElemType e)
{
    if((*s).top-(*s).base>=(*s).stacksize)
    {
        (*s).base=(SElemType *)realloc((*s).base,((*s).stacksize+ increment )*sizeof(SElemType));
        if(!(*s).base)
            exit(0);
        (*s).top=(*s).base+(*s).stacksize;
        (*s).stacksize+=increment;
    }
    *((*s).top)++=e;
    return 1;
}

int Pop(SqStack *s,SElemType *e)
{
    if((*s).top==(*s).base)
        return 0;
    *e=*(--(*s).top);
    return 1;

}
int StackEmpty(SqStack s)
{
    if(s.top==s.base)
        return 1;
    else
        return 0;

}
void NextPos(PosType *c,PosType t,int d)
{
    switch(d)
    {
        case 1: (*c).x=t.x;(*c).y=t.y+1;break;
        case 2: (*c).x=t.x+1;(*c).y=t.y;break;
        case 3: (*c).x=t.x;(*c).y=t.y-1; break;
        case 4: (*c).x=t.x-1;(*c).y=t.y; break;
    }
    
}
void draw1(PosType curpos)
{
    gotoxy(curpos.y+1,curpos.x+1);
    printf("o");
}
void draw2(void)
{
    int i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            if(maze[i][j]==1)
                printf("*");
            else
                printf(" ");
        }
        printf("\n");
     }
}
int MazePath(PosType start,PosType end)
{
    SqStack s;
    PosType curpos;
    SElemType e;
    SElemType *p;
    int curstep,total=0;
    int num[11]={0},min,i;


    InitStack(&s);
    curpos=start;
    curstep=1;

    do
    {

        if(maze[curpos.x][curpos.y]==0)
        {
            gotoxy(1,1);draw2();draw1(curpos); sleep(1);;
            if(equal(curpos,end))
            {
                p=s.base;i=0;
                while(p!=s.top)
                {
                    gotoxy(p->seat.y+1,p->seat.x+1);
                    printf("o");
                    p++;
                    i++;
                }
                total++;
                num[total]=i;
                gotoxy(2,13+2*total);
                printf("No.%d:",total);
                p=s.base;
                while(p!=s.top)
                {
                    printf("[%d,%d]->",p->seat.x,p->seat.y);
                    p++;
                }




                getch();
                Pop(&s,&e);
                gotoxy(1,1);draw2();draw1(e.seat); sleep(1);;
                while(e.di==4&&!StackEmpty(s))
                {
                    maze[e.seat.x][e.seat.y]=2;
                    Pop(&s,&e);
                    gotoxy(1,1);draw2();draw1(e.seat); sleep(1);;
                }
                if(e.di<4)
                {
                    e.di++;
                    Push(&s,e);
                    NextPos(&curpos,e.seat,e.di);

                }


               continue;

            }
            maze[curpos.x][curpos.y]=2;
            e.ord=curstep;
            e.seat=curpos;
            e.di=1;
            Push(&s,e);



            NextPos(&curpos,curpos,1);

            curstep++;
        }
        else
        {
            if(!StackEmpty(s))
            {
                Pop(&s,&e);
                while(e.di==4&&!StackEmpty(s))
                {
                    maze[e.seat.x][e.seat.y]=0;
                    Pop(&s,&e);
                    gotoxy(1,1);draw2();draw1(e.seat); sleep(1);;
                }
                if(e.di<4)
                {
                    e.di++;
                    Push(&s,e);
                    NextPos(&curpos,e.seat,e.di);

                }

            }
        }
    }while(!StackEmpty(s));
    gotoxy(2,15+2*total);

    min=1;
    for(i=1;num[i]!=0;i++)
        if(num[i]<num[min])
            min=i;
    printf("The shortest way is No.%d.\n",min);
    printf("Finish.");
    return 0;

}


main()
{


    PosType start,end;
    gotoxy(1,1);
    draw2();
    start.x=1;
    start.y=0;
    end.x=5;
    end.y=9;



   MazePath(start,end);

   getch();


}