Again About Horses#3740
On an 8 \times 8 chessboard, you are given two distinct squares.
Your task is to determine the shortest path a knight can take to move from the first square to the second.
The input consists of the coordinates of two squares. Each coordinate is represented by two characters: the first is a lowercase letter from to , and the second is a digit from to , such as . Each square's coordinates are provided on a separate line.
The output should be a sequence of squares, beginning with the first square and ending with the second. Each pair of consecutive squares in the sequence must be connected by a knight's move, and the total number of squares in the sequence should be minimized.
Example 1