UVA-439 - Knight Moves

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161004 大學程式能力檢定 CPE」題目。
• 相同題目：ZOJ-c117

題意概要

關於西洋棋中騎士旅行問題 (Traveling Knight Problem)：題目給定騎士所在的起始格子 $X$ 與終點格子 $Y$，試求該騎士從 $X$ 走到 $Y$ 最少需要移動多少步？

• 分析：本題為「廣度優先搜尋 (BFS)」的應用。在西洋棋中，騎士的走法是在 $2 \times 3$ 的格子中以對角線的移動，如下圖所示。在使用 BFS 的過程，可以使用「佇列 (queue)」模擬 (記得：#include <queue>)，唯獨要注意，當一個位置進入佇列時，就要將該位置封閉，避免該位置再次進入佇列而發生 TLE 的錯誤。

Input

The input file 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.

Output

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

Sample Input

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

Sample Output

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.