算法分析

本题有个算法的实现bfs,dfs,Floyd都可以.

dfs
用深搜的话就是向8个方向递归,计算从起点到终点的最短距离.
bfs
广搜也是向8个方向搜索,不过是把值都放进队列里,这样避免重复搜.
Floyd
这是解决表格问题最常用的算法,将棋盘上任意两点的距离全都保存起来,对所有的输入直接查表.

程序代码

dfs

#include <stdio.h>
#include <memory.h> 
int knight[8][8];//棋盘
int x[]={-1,1,2,2,1,-1,-2,-2};//八个方向 
int y[]={2,2,1,-1,-2,-2,-1,1};
void DFS(int si,int sj,int moves)
{
    if(si<0||sj<0||si>=8||sj>=8||moves>=knight[si][sj])    return ;
    knight[si][sj]=moves;
    int i;
    for(i=0;i<8;i++)
    {
        DFS(si+x[i],sj+y[i],moves+1);
    }
}
int main()
{
    int i,j;
    char a[10],b[10];
    while(scanf("%s%s",a,b)!=EOF)
    {
        memset(knight,10,sizeof(knight));
        DFS(a[0]-'a',a[1]-'1',0);
        printf("To get from %s to %s takes %d knight moves.\n",a,b,knight[b[0]-'a'][b[1]-'1']);
    }
    return 0;
}

bfs

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,-2,-1,1,2};
struct Point{
    int x,y;
    int move; 
};
Point a,b;
void bfs()
{

    queue<Point> q;
    while(!q.empty())q.pop();
    q.push(a);
    while(true)
    {
        Point p=q.front();
        q.pop();
        if(p.x==b.x&&p.y==b.y){b.move=p.move;break;}
        for(int i=0;i<8;i++)
        {
            Point k;
            k.x=p.x+dx[i];
            k.y=p.y+dy[i];
            if(k.x>7||k.x<0||k.y>7||k.y<0)    continue;
            k.move=p.move+1;
            q.push(k);            
        }
    }

}
int main()
{
    char ch1[3],ch2[3];
    while(scanf("%s%s",ch1,ch2)!=EOF)
    {
        a.x=ch1[1]-'1'; a.y=ch1[0]-'a';
        b.x=ch2[1]-'1'; b.y=ch2[0]-'a';
        a.move=b.move=0;
    bfs();
    cout<<"To get from "<<ch1<<" to "<<ch2<<" takes "<<b.move<<" knight moves."<<endl; 
    }
    return 0;
}

Floyd

#include <stdio.h>
int i,j,m;
//计算棋盘上任意两格之间的最短路径 
void shortested(int k[][64])
{
    //计算骑士走一步可以到达的位置 
    int x,y;
    for(i=0;i<64;k[i][i]=0,++i)
        for(j=0;j<64;++j)
        //棋盘上两格之间的相对位置 
        {
            x=abs(i/8-j/8);
            y=abs(i%8-j%8);
            if(x==1&&y==2||x==2&&y==1)
                k[i][j]=k[j][i]=1;//只需要跳一步 
        }
    //通过Floyd算法,计算棋盘上其他两格之间的最短路径
    for(m=0;m<64;++m)
        for(i=0;i<64;++i)
            for(j=0;j<64;++j)
                if(k[i][m]+k[m][j]<k[i][j])
                    k[i][j]=k[i][m]+k[m][j]; 
}
int main()
{
    //保存棋盘上任意两点之间的最短路径
    int knight[64][64];
    //初始为∞
    for(i=0;i<64;++i)
        for(j=0;j<64;++j)
            knight[i][j]=10;
    shortested(knight);

    char s[5],t[5];
    while(scanf("%s%s",s,t)!=EOF)
    {
        int x=(s[0]-'a')+(s[1]-'1')*8;
        int y=(t[0]-'a')+(t[1]-'1')*8;
        printf("To get from %s to %s ",s,t);
        //直接查表输出结果
        printf("takes %d knight moves.\n",knight[x][y]); 
    }
    return 0;
}

总结

开始这个问题之前,要知道骑士是怎么走的,我百度了下才知道是走斜对角线的.
至于bfs算法,我一开始有点搞不懂,因为算最短路径,应该有比较函数呀!,但后来我想明白了,因为是枚举式的检索,只要到达终点,就一定是最短路径.