UVa 439

439 - Knight Moves

• http://acm.uva.es/p/v4/439.html

Summary

Exercise your ability to write a Breadth-First Search.

Explanation

We are given the starting point and an ending point of a knight on an ordinary 8x8 chessboard. We have to determine the minimal number of moves for a knight to get from the starting point to the ending point. We can view the chessboard as a Graph, where the nodes are positions in the board, and the edges in the graph are positions that a knight can reach in a single move. Then it is clear that the minimal number of moves for the knight to reach the destination is the length of the Shortest Path on the induced graph. Thus, a Breadth-First Search from the start to the end will give the correct answer. As an alternative, one can also use Lee's algorithm on an 8x8 matrix.

Input

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

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.