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
hide comments
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
AC IN ONE GO!
|
|
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.
|
|
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 |
|
secret1:
2017-02-02 06:33:30
CAN IT BE SOLVED USING DFS?
|
|
a1796:
2017-01-01 21:54:11
ny first bfs :D |
|
domino2016:
2016-11-26 16:05:07
Interesting problem
|
|
rishabh_nitw:
2016-10-17 05:31:08
basic bfs ...good to learn. |
|
suraj_:
2016-10-15 17:12:35
good implementation of BFS!
|
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 |