迷宫问题

/*
 *题二：求解迷宫的一条最短路径，要求：用栈和队列实现，
 *不允许使用递归算法。问题描述见教材第50页“3.2.4 迷宫求解”。
 */

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100

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

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

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

int InitStack (SqStack *S)
{
    S->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->base)
         exit (OVERFLOW);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}

int GetTop (SqStack S, ElemType *e)
{
    if (S.top==S.base)
        return ERROR;
    *e=*(S.top-1);
    return OK;
}

int Push (SqStack *S, ElemType e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base=(ElemType *)realloc(S->base,
                              (S->stacksize + STACKINCREMENT)* sizeof(ElemType));
        if (!S->base)
            exit (OVERFLOW);
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
    }
    *S->top++ = e;
    return OK;
}

int Pop(SqStack *S,ElemType *e)
{
    if (S->top==S->base)
        return ERROR;
    *e=*(--S->top);
    return OK;
}

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

void ShowAll (SqStack *S)
{
    ElemType t;
    printf ("h  l  step\n");
    while (1)
    {
        if (Pop (S, &t))
        {
            printf ("%d  %d  %d\n", t.seat.x, t.seat.y, t.ord);
        }
        else
            break;
    }
}

void Change (SqStack *From, SqStack *To) /* 逆置矩阵 */
{
    ElemType t;
    while (1)
    {
        if (Pop (From, &t))
            Push (To, t);
        else
            break;
    }
}

int Pass(int maze[10][10], PosType local) /*当前位置是否可走*/
{

    if (maze[local.x][local.y]==1)
        return 0;
    else
        return 1;
}

void FootPrint (int maze[10][10],PosType local)/*修改当前位置为1*/
{
    maze[local.x][local.y]=1;
}

PosType NextPos (PosType local ,int i)
{
    if (i==1)
    {
        local.y+=1;
    }
    else if (i==2)
    {
        local.x+=1;
    }
    else if (i==3)
    {
        local.x-=1;
    }
    return local;
}

void MarkPrint (int maze[10][10],PosType local)/*修改当前位置为1*/
{
    maze[local.x][local.y]=1;
}

int MazePath (int maze[10][10],PosType start,PosType end,SqStack *S)
{
    PosType local = start;
    ElemType temp;
    int step=1;
    do {
        if (Pass (maze, local))
        {
            FootPrint (maze, local);
            temp.ord=step;
            temp.seat=local;
            temp.di=1;
            Push (S,temp);
            if (Equal(local, end))
                return OK;
            local = NextPos (local ,1);
            step++;
        }
        else
        {
            if (!StackEmpty(*S))
            {
                Pop(S,&temp);
                while (temp.di==4&&!StackEmpty(*S))
                {
                    MarkPrint (maze,temp.seat);
                    Pop (S,&temp);
                    step--;
                }
                if (temp.di<4)
                {
                    temp.di++;
                    Push (S,temp);
                    local=NextPos(temp.seat, temp.di);
               }
            }

        }
     }while (!StackEmpty (*S));
     return ERROR;
}

int Equal (PosType A,PosType B)
{
    if (A.x==B.x&&A.y==B.y)
        return 1;
    else
        return 0;
}


int main ()
{
    PosType start,end;
    SqStack s;
    int result=0;
    int maze [10][10] =
    { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
      {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
      {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
      {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
      {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
      {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
      {1, 0, 1, 0, 0, 0, 1, 0, 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}};
    start.x=1;
    start.y=1;
    end.x=8;
    end.y=8;
    InitStack (&s);
    result=MazePath (maze, start, end, &s);
    if (result)
    {
        printf ("found\n");
        ShowAll(&s);
    }
    else
        printf ("not found");
    getchar();
    return 0;
}