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).
Input
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.
Output
Print the minimum number of moves a knight takes to reach from start to destination in a separate line.
Constarints
1 <= T <= 4096
Example
Input: 3 a1 h8 a1 c2 h8 c3 Output: 6 1 4
hide comments
vishesh197:
20171014 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: 20171014 06:38:27 

sfialok98:
20170628 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 ..!!


epsilonalpha:
20170626 02:28:49
AC in one go! 

Rajat Gautam:
20170612 22:01:25
If facing run time error make sure to give space to nul charater of string for storing. 

invinci:
20170611 20:18:09
building the graph took me half an hour, otherwise easy bfs problem, anyways AC in one go ;) 

akash619j:
20170502 13:22:00
AC in one go! Thanks to queue and pair stl in c++ :) 

nilabja16180:
20170402 09:16:10
AC IN ONE GO!


holmesherlock:
20170325 20:00:19
damn irritating runtime error for a very stupid statement missing,otherwise enjoyed doing it 

vladimira:
20170302 16:32:15
Very tricky, at first I thought it is an easypizy one.


devbishnoi:
20170205 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: 20170205 18:53:26 
Added by:  Nakul Krishna 
Date:  20120930 
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 