#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define STACK_INIT_SIZE 70
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;
bool InitStack(SqStack &S)
//构造一个空栈S
{
    S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base)exit(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return 1;
}
bool GetTop(SqStack S,SElemType &e)
//若栈不空，则用e返回S的栈顶元素，并返回1；否则返回0
{
    if(S.top==S.base)return 0;
    e=*(S.top-1);
    return 1;
}
bool Push(SqStack &S,SElemType e)
//插入元素e为新的栈顶元素
{
    *S.top++=e;
    return 1;
}
bool Pop(SqStack &S,SElemType &e)
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0
{
    e=*--S.top;
    if(S.top==S.base)return 0;
    return 1;
}
bool Pass(SqStack S,PosType curpos)
{
    SElemType e;
    if(curpos.x<0||curpos.x>7||curpos.y<0||curpos.y>7)return 0;
    while(S.top!=S.base)
    {
        e=*--S.top;
        if(curpos.x==e.seat.x&&curpos.y==e.seat.y)return 0;
    }
    return 1;
}
PosType NextPos(PosType curpos,int di)
{
    int HTry1[8]={-2,-1,1,2,2,1,-1,-2};
    int HTry2[8]={1,2,2,1,-1,-2,-2,-1};
    PosType s;
    s.x=curpos.x+HTry1[di];
    s.y=curpos.y+HTry2[di];
    return(s);
}
bool Path(SqStack &S,PosType start)
{
    int curstep;
    PosType curpos;
    SElemType e;
    InitStack(S);
    curpos=start;
    curstep=1;
    do
    {
        if(Pass(S,curpos))
        {
            e.ord=curstep;
            e.seat=curpos;
            e.di=0;
            Push(S,e);
            if(curstep==65)return 1;
            curpos=NextPos(curpos,0);
            curstep++;
        }
        else
        {
            if(S.top!=S.base)
            {
                Pop(S,e);
                curstep--;
                while(e.di==7&&S.top!=S.base)
                {
                    Pop(S,e);
                    curstep--;
                }
                if(e.di<7)
                {
                    e.di++;
                    e.ord=curstep;
                    Push(S,e);
                    curstep++;
                    curpos=NextPos(e.seat,e.di);
                }
            }
        }
    }while(S.top!=S.base);
    return 0;
}
int main()
{
    int a[8][8],i,j;
    SqStack S;
    PosType start;
    SElemType b;
    for(i=0;i<8;i++)
        for(j=0;j<8;j++)
        {
            a[i][j]=0;
        }
    printf("指定马的初始位置：");
    scanf("%d%d",&start.x,&start.y);
    while(start.x<0||start.x>7||start.y<0||start.y>7)
    {
        printf("初始位置超出棋盘范围，请重新输入初始位置:");
        scanf("%d%d",&start.x,&start.y);
    }
    if(Path(S,start))
    {
        while(S.top!=S.base)
        {
            b=*--S.top;
            a[b.seat.x][b.seat.y]=b.ord;
        }
        printf("按求出的行走路线，输出矩阵:\n");
        for(i=0;i<8;i++)
        {
            for(j=0;j<8;j++)
                printf("%02d ",a[i][j]);
            printf("\n");
        }
    }
    else printf("找不到行走路径.\n");
    return 0;
}

[[it] 本帖最后由 aluily 于 2008-4-20 13:06 编辑 [/it]]