骑士移动问题 实现的三种算法 POJ 2243，ZOJ 1091

经典的TKP问题，在8*8的棋盘上，问骑士（相当于中国象棋中的马）从一点移动到另一点至少需要走一步。 应该是有三种解法，DFS,BFS，和 floyd 打表求出每两点之间的最短

路，笔者亲测，程序的运行速度应该是floyd > BFS > DFS，下面给出三种代码。

//DFS版本

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
int knight[8][8];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
void DFS(int x,int y,int step)
{
    if(x<0 || x>7 || y<0 || y>7 || step>=knight[x][y])
         return ;
    knight[x][y]=step;
    for(int i=0;i<8;i++)
    {
        DFS(x+dx[i],y+dy[i],step+1);
    }
}
int main()
{
    char s[5],t[5];
    while(scanf("%s %s",s,t)!=EOF)
    {
        memset(knight,10,sizeof(knight));
        DFS(s[0]-a,s[1]-1,0);
        printf("To get from %s to %s takes %d knight moves.
",s,t,knight[t[0]-a][t[1]-1]);
    }
    return 0;}

//BFS版本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
struct Point
{
    int x;
    int y;
    int step;
}from,to;
int main()
{
    queue<Point> q;
    char s[5],t[5];
    int x[]={1,1,-1,-1,2,2,-2,-2};
    int y[]={2,-2,2,-2,1,-1,1,-1};
    while(scanf("%s %s",s,t)!=EOF)
       {
           while(!q.empty()) q.pop();
           from.x=s[0]-a;
           from.y=s[1]-1;
           from.step=0;
           to.x=t[0]-a;
           to.y=t[1]-1;
           q.push(from);
           Point tmp;
           while(q.size())
           {
               from=q.front();
               q.pop();
               if(from.x==to.x && from.y==to.y)
                    break;
               for(int i=0;i<8;i++)
               {
                   tmp.x=from.x+x[i];
                   tmp.y=from.y+y[i];
                   tmp.step=from.step+1;
                   if(tmp.x>=0&&tmp.x<8&&tmp.y>=0&&tmp.y<8)
                     q.push(tmp);
               }
           }
        printf("To get from %s to %s takes %d knight moves.
",s,t,from.step);
       }
       return 0;
}

//FLOYD版本 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxn = 64;
void floyd(int dis[][64])
{
    for(int i=0;i<64;dis[i][i]=0,i++)
        for(int j=0;j<64;j++)
    {
        int x=abs(i/8-j/8);
        int y=abs(i%8-j%8);
        if((x==1 && y==2) || (x==2 && y==1))
            dis[i][j]=dis[j][i]=1;
    }
    for(int m=0;m<64;m++)
        for(int i=0;i<64;i++)
          for(int j=0;j<64;j++)
             dis[i][j] = min (dis[i][j],dis[i][m]+dis[m][j]);
}
int main()
{
    int dis[maxn][maxn];
    for(int i=0;i<64;i++)
        for(int j=0;j<64;j++)
           dis[i][j]=10;
    floyd(dis);
    char s[5];
    char t[5];
    while(scanf("%s %s",s,t)!=EOF)
    {
        int x = (s[0]-a)*8+(s[1]-1);
        int y = (t[0]-a)*8+(t[1]-1);
        printf("To get from %s to %s takes %d knight moves.
",s,t,dis[x][y]);
    }
    return 0;
}