PKU 2243. Knight Moves

나이트의 움직임

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3541	Accepted: 2177

설명

당신의 친구가 TKP 를 조사하고 있고, 당신은 막혀진 공간에서의 나이트의 움직임을 조사해야 하는데 그 조사할 움직임은 주어진 n개의 정사각형 칸들을 한번에 움직이는 방법입니다. 그가 생각하기로, 문제의 가장 어려운 부분은 두 개의 주어진 정사각형의 칸을 나이트가 최소한으로 움직이는 숫자를 결정하는 것이고, 이것은 당신이 예전에 해냈던 것이므로, 찾아내는 것은 쉬울 것입니다.
물론 당신은 그것이 문제를 푸는 그 자체라는 것 또한 알고 있습니다. 그래서 당신은 그 친구에게 "어려운" 부분을 풀 프로그램을 짜도록 제안합니다.

당신이 해야 할 일은 두 정사각형 a 와 b를 입력받고서 a에서 b까지 나이트가 최단거리로 움직이려면 얼마나 이동해야 하는지를 결정하는 프로그램을 짜는 것입니다.

입력

입력은 하나 혹은 더 많은 테스트 케이스들로 이루어집니다. 각 테스트 케이스는 하나의 줄을 포함하는데, 이 줄에는 한 칸짜리의, 떨어진 2개의 정사각형들이 들어갑니다. 정사각형은 체스판의 열을 나타내는 문자(a-h)와 행을 나타내는 숫자(1-8)의 문자열로 이루어져 있습니다.

출력

각 테스트 케이스에 대해서 하나의 줄로 나타내어지는데, "xx에서 yy까지 움직이는데 나이트가 n번 움직여야 한다" 라는 표현을 씁니다.

입력 예시

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.

Source

Ulm Local 1996