Hide

Knight Walk

Before we get into the problem, let’s go over algebraic notation in chess. Algebraic notation refers to the ‘names’ of the squares on a chessboard. Starting from left to right (from white’s perspective), the columns are named a–h. The rows are then named $1$$8$ in increasing order (again from white’s perspective). Each square’s ‘name’ is the column letter followed by the row number of that particular square.

/problems/mines21.knightwalk/file/statement/en/img-0001.png
Photo retrieved from wikipedia.org. Image Source

In Chess, a knight’s move is unique. It may move two squares horizontally and one square vertically, or two squares vertically and one square horizontally (with both forming the shape of an L). For example, a knight on d3 can move to c1, b2, b4, c5, e5, f4, f2, and e1.

It takes (at least) two moves for a knight on d3 to move to d5, with two possible shortest paths: d3 $\rightarrow $ b4 $\rightarrow $ d5 and d3 $\rightarrow $ f4 $\rightarrow $ d5. There are other possible paths (d3 $\rightarrow $ f2 $\rightarrow $ g4 $\rightarrow $ f6 $\rightarrow $ d5 is one), but they are not one of the shortest paths.

Your task is as follows: given the position of a knight on a chessboard and a target square, both in algebraic notation, find all of the possible shortest paths for the knight to move from its starting position to the target square.

Input

Input is the location of the knight in algebraic notation, followed by the target square on the following line. It is guaranteed that the initial location and target square will be distinct, valid squares.

Output

Output is all of the shortest paths in alphabetical order (c1 comes before d1, a1 comes before a2, etc) with each path on its own line, in the following format: starting_square -> square2 -> …-> target_square.

Sample Input 1 Sample Output 1
d3
d5
d3 -> b4 -> d5
d3 -> f4 -> d5
Sample Input 2 Sample Output 2
a6
c8
a6 -> b4 -> c6 -> a7 -> c8
a6 -> b4 -> c6 -> e7 -> c8
a6 -> b4 -> d5 -> b6 -> c8
a6 -> b4 -> d5 -> e7 -> c8
a6 -> b8 -> c6 -> a7 -> c8
a6 -> b8 -> c6 -> e7 -> c8
a6 -> b8 -> d7 -> b6 -> c8
a6 -> c5 -> a4 -> b6 -> c8
a6 -> c5 -> b7 -> d6 -> c8
a6 -> c5 -> d7 -> b6 -> c8
a6 -> c5 -> e4 -> d6 -> c8
a6 -> c7 -> a8 -> b6 -> c8
a6 -> c7 -> b5 -> a7 -> c8
a6 -> c7 -> b5 -> d6 -> c8
a6 -> c7 -> d5 -> b6 -> c8
a6 -> c7 -> d5 -> e7 -> c8
a6 -> c7 -> e8 -> d6 -> c8
CPU Time limit 3 seconds
Memory limit 1024 MB
Author
John Henke
Source [email protected] High School Programming Competition 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in