NAKANJ - Minimum Knight moves !!!

Anjali and Nakul are good friends. They both had a quarrel recently while playing chess. Nakul wants to know the minimum number of moves a knight takes to reach from one square to another square of a chess board (8X8). Nakul is brilliant and he had already written a program to solve the problem. Nakul wants to know whether Anjali can do it. Anjali is very weak in programming. Help her to solve the problem.

A knight can move in the shape of an "L" in a chessboard - two squares either forward, backward, left, or right and then one square to its left or right. A knight move is valid if it moves as mentioned above and it is within the boundary of the chessboard (8 X 8).


There are T test cases in total. The next T lines contain two strings (start and destination) separated by a space.

The strings start and destination will only contain two characters - First character is an alphabet between 'a' and 'h' (inclusive), Second character is a digit between '1' and '8' (inclusive) - (Quotes just for clarity).

To know the knight moves more clearly refer to the above figure.


Print the minimum number of moves a knight takes to reach from start to destination in a separate line.


1 <= T <= 4096


a1 h8
a1 c2
h8 c3


hide comments
vishesh197: 2017-10-14 06:38:06

very good problem for learning where to apply dfs and where to apply bfs.....focus on this question before solving the problem

Last edit: 2017-10-14 06:38:27
sfialok98: 2017-06-28 21:15:55

After 1st unsuccessful attempt,I was afraid ,how many attempts is this quesion going to take,but got It accepted in the 2nd attempt ..!!

Last edit: 2017-06-28 21:16:25
epsilonalpha: 2017-06-26 02:28:49

AC in one go!

Rajat Gautam: 2017-06-12 22:01:25

If facing run time error make sure to give space to nul charater of string for storing.

invinci: 2017-06-11 20:18:09

building the graph took me half an hour, otherwise easy bfs problem, anyways AC in one go ;)

akash619j: 2017-05-02 13:22:00

AC in one go! Thanks to queue and pair stl in c++ :)

nilabja16180: 2017-04-02 09:16:10

1st chess problem!

holmesherlock: 2017-03-25 20:00:19

damn irritating runtime error for a very stupid statement missing,otherwise enjoyed doing it

vladimira: 2017-03-02 16:32:15

Very tricky, at first I thought it is an easy-pizy one.
Why pypy solve in 0.06s when cpython in 0.01s? Usually it is the other way round.
Another question: why my python uses 2.5x times more memory comparing to other people in all the problems I've solved (40+ problems)?

=(Francky)=> With the changes of compilers, and versions (eg Python), we have some changes with the memory used. Many info about old submissions such time, memory are not reliable with some new submissions.

@Francky thx =)

Last edit: 2017-03-02 20:32:04
devbishnoi: 2017-02-05 18:52:54

U need to find minimum no of moves. And here it costs 1 in each move so bfs also can work. DFS cannot work here.

Last edit: 2017-02-05 18:53:26

Added by:Nakul Krishna
Time limit:0.165s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Used for Code it - Vidyut 2012 - Amrita University