UVa 439

From Algorithmist
Jump to navigation Jump to search

439 - Knight Moves[edit]

Summary[edit]

Exercise your ability to write a Breadth-First Search.

Explanation[edit]

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[edit]

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

Output[edit]

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.

Solutions[edit]