[递归,步数最少] 骑士游历

骑士游历（5000/s)

题目描述

    “骑士游历”问题是一道经典的问题：从8*8棋盘上的一点a出发，到另一点b的最短距离是多少？当然，骑士只能按照“日”字形走法来前进。
    如何快速地得到这个问题的解？我们需要你在1秒的时间内算出至多5000组这样的问题。

关于输入

输入包括多行
每行是两个坐标，表示起点和终点

关于输出

对于每个输入，输出最短步数（具体格式见样例）

例子输入

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（双向BFS会更加优化）

解题分析

本题可以使用递归来解决，我们按照马走的步法，定义两个用来移动的数组dx，dy。然后，我们初始化棋盘中的数全为0，并且从起始点开始我们的骑士游历，同时维护一个变量n，并在每次更新这个n，代表这是第n步。当我们游历到某点时，我们便把这个步数赋值给棋盘中相应位置，下次再遍历的时候，我们需要观察是否这次的步数小于上次的步数（如果大于就不用看了，肯定不是最少步数），并不断地遍历即可。

代码实现

#include 
#include 
#include 
#include 
using namespace std;
 
const int dx[]={-2,-1,1,2,2,1,-1,-2};
const int dy[]={1,2,2,1,-1,-2,-2,-1};
int board[9][9]={0};
int minn=INT32_MAX;
 
void f(int x1,int y1,int x2,int y2,int n){
    for(int i=0;i<8;i++){
        int nx=x1+dx[i],ny=y1+dy[i];
        if(nx>=1 && nx<=8 &&ny>=1 && ny<=8){
            if(board[nx][ny]>n || board[nx][ny]==0){
                if(nx==x2 && ny==y2){
                    minn=min(minn,n);
                }
                else{
                    board[nx][ny]=n;
                    f(nx,ny,x2,y2,n+1);
                }
            }
        }
    }
}
 
int main() {
	string d1,d2;
	while(cin>>d1){
	    cin>>d2;
	    minn=INT32_MAX;
	    memset(board,0,sizeof(board));
	    int x1=d1[0]-'a'+1,y1=d1[1]-'0';
	    int x2=d2[0]-'a'+1,y2=d2[1]-'0';
        if(x1==x2 && y1==y2){
        cout<<"To get from "<" to "<" takes "<<0<<" knight moves."<continue;
        }
        f(x1,y1,x2,y2,1);
        cout<<"To get from "<" to "<" takes "<" knight moves."<
	    }
	return 0;
}