算法设计：骑士问题

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

#define MAXSTEP 64
#define B 2
#define N 1

int countStep;

//check if (x,y) can be moved to

int check(int x,int y,int chessboard[8][8])
{
    if(x<0||x>7||y<0||y>7||chessboard[x][y]==B) return B;
    else return(chessboard[x][y]);
}

void moves(int x,int y,int chessboard[8][8],int count)
{
    int tChessboard[8][8],i,j;

    //copy the chessboard

    for(i=0;i<8;i++) for(j=0;j<8;j++) tChessboard[i][j]=chessboard[i][j];
    switch(check(x,y,tChessboard))
    {
    case B:return;
    case N:if(count<countStep) countStep=count;return;
    default:
        if(count+1<countStep)
        {
            tChessboard[x][y]=B;
            moves(x+2,y+1,tChessboard,count+1);
            moves(x+2,y-1,tChessboard,count+1);
            moves(x-2,y+1,tChessboard,count+1);
            moves(x-2,y-1,tChessboard,count+1);
            moves(x+1,y+2,tChessboard,count+1);
            moves(x+1,y-2,tChessboard,count+1);
            moves(x-1,y+2,tChessboard,count+1);
            moves(x-1,y-2,tChessboard,count+1);
        }
    }
}

int main()
{
    int startX,startY,chessboard[8][8],n,i,j;
    char s[3];

    typedef struct trst
    {
        int result;
        struct trst *next;
    }rst;

    rst *head,*p;
    head=p=(rst*)malloc(sizeof(rst));
    p->next=NULL;
    while(1)
    {
        //input

        scanf("%d",&n);
        if(n==-1) break;
        //inital

        countStep=MAXSTEP;
        for(i=0;i<8;i++) for(j=0;j<8;j++) chessboard[i][j]=0;
        if(n)
        {
            for(i=0;i<n;i++)
            {
                scanf("%s",s);
                chessboard[(s[0]-'a')][(s[1]-'1')]=B;
            }
        }
        scanf("%s",s);
        startX=s[0]-'a';startY=s[1]-'1';
        scanf("%s",s);
        chessboard[(s[0]-'a')][(s[1]-'1')]=N;
        //locate

        p->next=(rst*)malloc(sizeof(rst));
        p=p->next;
        p->next=NULL;
        //call solve funtion

        moves(startX,startY,chessboard,0);
        p->result=countStep;
    }
    //output

    p=head->next;
    i=1;
    while(p)
    {
        if(p->result==MAXSTEP) printf("Board %d:not reachable\n",i);
        else printf("Board %d:%d moves\n",i,p->result);
        p=p->next;
        i++;
    }
}