HUSTOJ

Description

你的一个朋友正在研究旅行骑士问题（TKP），需要找到最短的、封闭的骑士移动路线，对给定正N方型国际象棋棋盘上的每一个方格旅行一次。
他认为问题中最困难的部分是确定两个给定方格之间骑士移动的次数，一旦你完成了这一点，整个旅行则非常简单。
当然，你知道，反之亦然。所以你让他写一个程序来解决“困难”部分。
你的工作是写一个程序，以两个方格A和B作为输入，然后确定骑士从A到B的最短路线上移动的次数。

Input

输入文件将包含一个或多个测试用例。每个测试用例由一行包含两个方格的数据组成、方格数据由空格分开。
国际象棋棋盘上，方格数据由2个字母表示，其中：(a-h)的字母表示列、(1-8)的数字表示行

Output

对于每个测试用例，打印一行：To get from xx to yy takes n knight moves.

Sample Input Copy

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

Sample Output Copy

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.

HINT

国际象棋棋盘骑士移动类似于中国象棋中的马走日

Source/Category

BFS 其他 2016 level5