OpenJudge - 2243:Knight Moves

2243:Knight Moves

描述

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

输入

The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

输出

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

骑士移动

你的一位朋友正在研究移动骑士问题（TKP），你要找到骑士移动的最短闭合骑士，骑士移动只访问棋盘上给定n个方格集合的每个方格一次。他认为，问题最困难的部分是确定两个给定方块之间骑士移动的最小数量，一旦你完成了这一点，找到巡演将很容易。

你当然知道，反之亦然。所以你让他写一个程序来解决“困难”的部分。

你的工作是编写一个程序，将两个正方形a和b作为输入，然后确定骑士在从a到b的最短路线上移动的次数。

输入：

输入将包含一个或多个测试用例。每个测试用例由一行组成，其中包含两个由一个空格分隔的正方形。正方形是一个字符串，由代表列的字母（A-h）和代表棋盘上行的数字（1-8）组成。

输出：

对于每个测试用例，打印一行“从xx到yy需要n个骑士移动”。