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
|
||||||||||||||
2021-11-16 20:09:43
AC in one go!! (hint: Use BFS on 2D grid) |
||||||||||||||
2021-10-23 05:41:58
Can anyone check why when i submit all the "&&" in my c++ code become &¤,giving me compile error? Thank you. Edit: && current;=&¤t; ,since & curren is ¤ Last edit: 2021-10-23 05:58:58 |
||||||||||||||
2021-10-14 04:39:16
ainem, I think you've forgotten set visited[stx][sty] to true at the beginning of BFS function. |
||||||||||||||
2021-10-14 04:25:32
My first comment, great problem, many people suggest the correct answer, I tried dx, dy movements, and checked if it belongs to a valid position. |
||||||||||||||
2021-10-08 13:05:33
why my solution got WA, i've tried all the tests https://ideone.com/K5RINV |
||||||||||||||
2021-08-24 22:50:07
feel great after solving this problem |
||||||||||||||
2021-06-10 13:53:43 Waseem Ahmed
AC in one go finally!! Simple BFS. Used (char) +/- 1 or 2 for both characters to get next move. [8 combinations] Check if new move is valid If yes, add to queue |
||||||||||||||
2021-04-26 23:16:50
can use alias like this(key : value pair) {{a: 1},{b: 2},{c: 3},{d: 4},{e: 5},{f: 6},{g: 7},{h: 8}} |
||||||||||||||
2021-04-16 21:42:36
TEST CASES not good. As from x = 4, y = 4 to x = 4 y = 4. ans is 0. But my code were failing but still got accepted. |
||||||||||||||
2021-04-01 08:42:29
Why am I getting WA? My code seems to give right answers. Please help me. |