Submit | All submissions | Best solutions | Back to list |
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 (8 × 8). 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 × 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.
Constraints
1 ≤ T ≤ 4096
Example
Input: 3 a1 h8 a1 c2 h8 c3 Output: 6 1 4
Added by: | Nakul Krishna |
Date: | 2012-09-30 |
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 |
hide comments
|
|||||||||||||
2012-12-20 10:15:25 Mostafa 36a2
Enjoy Solving Thanks :) Last edit: 2012-12-20 13:25:57 |
|||||||||||||
2012-11-26 09:47:55 Aditya Pande
also try http://www.spoj.pl/problems/NAKANJC/ Last edit: 2012-11-26 19:47:16 |
|||||||||||||
2012-10-27 15:18:59 sahil
what should be the o/p for a1 a1 0 or 2? It should be 0. Last edit: 2012-10-31 03:51:09 |
|||||||||||||
2012-10-21 14:54:37 gourav
how you all guys are doing it in 0.00 sec ? :-o great bros! ;) |
|||||||||||||
2012-10-10 19:40:10 virtuazx
heh heh nakki....FinallY .. (--) |
|||||||||||||
2012-09-30 15:28:52 (Tjandra Satria Gunawan)(曾毅昆)
Hmm, my fastest algo that got AC 0.00s in C, got 0.82s in python :-O |
|||||||||||||
2012-09-30 14:14:53 Aditya Pande
@Tjandra Satria Gunawan : ya thnx i missed a1 a1 case and your solution is better coz my solution took 0.02 seconds Last edit: 2012-12-18 15:44:01 |
|||||||||||||
2012-09-30 14:06:54 (Tjandra Satria Gunawan)(曾毅昆)
@Aditya Pande: If your algo complexity is arround O(8^4) then your algo is faster than my algo: O(17616). maybe this case help you: 4 a1 a1 a1 a2 f6 g7 g7 h8 |