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
sandy_912:
20191106 15:40:50
@admin getting time limit exceed error in python Last edit: 20191106 15:50:35 

jemmy_neutron:
20191002 06:07:07
Wrong answer :( Last edit: 20191002 19:35:49 

shikhar_may7:
20190925 13:42:47
convert (a1 h8) form to int type (11 88) using onebased indexing. then find the shortest path from 11 to 88 using bfs. 

huyss125634:
20190821 14:06:36
i got timelimit. why?


ashik_01:
20190801 08:17:07
Nice Problem 

scolar_fuad:
20190710 07:20:28
Nice problem just a normal bfs with direction array >>>


prak_marcose22:
20190626 20:02:19
ac in one go(:


dkkv0000:
20190511 07:29:52
oh god take care of indexing it is 1based costed me 5 WA's 

rohan_14:
20190421 09:08:05
good problem to learn when to apply dfs and when to apply bfs!!! 

dashubaba:
20190410 19:07:58
@Admin can you help me why I am getting wrong ans? 
Added by:  Nakul Krishna 
Date:  20120930 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Used for Code it  Vidyut 2012  Amrita University 