Knight Moves

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

思路：就一个BFS。

#include <stdio.h>

struct {
int x,y,count;
}start,end,que[10000];

int n,bottom,top;
bool vis[9][9];

void search()
{
    if(que[top].x==end.x && que[top].y==end.y) printf("%d knight moves.\n",que[top].count);
    else
    {
        vis[que[top].x][que[top].y]=1;

        if(que[top].x+1<=8 && que[top].y+2<=8 &&!vis[que[top].x+1][que[top].y+2])
        {
            que[bottom].x=que[top].x+1;
            que[bottom].y=que[top].y+2;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        if(que[top].x+1<=8 && que[top].y-2>=1 &&!vis[que[top].x+1][que[top].y-2])
        {
            que[bottom].x=que[top].x+1;
            que[bottom].y=que[top].y-2;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        if(que[top].x-1>=1 && que[top].y-2>=1 &&!vis[que[top].x-1][que[top].y-2])
        {
            que[bottom].x=que[top].x-1;
            que[bottom].y=que[top].y-2;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        if(que[top].x-1>=1 && que[top].y+2<=8 &&!vis[que[top].x-1][que[top].y+2])
        {
            que[bottom].x=que[top].x-1;
            que[bottom].y=que[top].y+2;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        if(que[top].x-2>=1 && que[top].y-1>=1 &&!vis[que[top].x-2][que[top].y-1])
        {
            que[bottom].x=que[top].x-2;
            que[bottom].y=que[top].y-1;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        if(que[top].x-2>=1 && que[top].y+1<=8 &&!vis[que[top].x-2][que[top].y+1])
        {
            que[bottom].x=que[top].x-2;
            que[bottom].y=que[top].y+1;
            que[bottom].count=que[top].count+1;
            bottom++;
        }


        if(que[top].x+2<=8 && que[top].y+1<=8 &&!vis[que[top].x+2][que[top].y+1])
        {
            que[bottom].x=que[top].x+2;
            que[bottom].y=que[top].y+1;
            que[bottom].count=que[top].count+1;
            bottom++;
        }


        if(que[top].x+2<=8 && que[top].y-1>=1 &&!vis[que[top].x+2][que[top].y-1])
        {
            que[bottom].x=que[top].x+2;
            que[bottom].y=que[top].y-1;
            que[bottom].count=que[top].count+1;
            bottom++;
        }

        top++;
        search();
    }
}

int main()
{
    char temp[10];
    int i,j;

    while(gets(temp) && temp[0])
    {
        start.x=temp[0]-‘a‘+1;
        start.y=temp[1]-‘0‘;
        end.x=temp[3]-‘a‘+1;
        end.y=temp[4]-‘0‘;

        printf("To get from %c%c to %c%c takes ",temp[0],temp[1],temp[3],temp[4]);

        for(i=1;i<=8;i++) for(j=1;j<=8;j++) vis[i][j]=0;
        bottom=1;
        top=0;
        que[0].x=start.x;
        que[0].y=start.y;
        que[0].count=0;

        search();
    }
}

Knight Moves

原文：http://blog.csdn.net/faithdmc/article/details/18826281