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-03-31 07:58:11
I am getting tle again and again. Can someone please help me to fix the issue? [NG]: Don't post any sources or links to it here, use forum for review or debug. BTW. your code is completely unreadable. Last edit: 2021-04-01 08:43:02 |
||||||||||||||
2021-02-05 14:38:50
AC in one go..very nice problem for learning |
||||||||||||||
2021-01-31 22:15:05
I this this problem only allows C and Cpp. Can some one please check why python3 is not accepted, with multiple WA's |
||||||||||||||
2020-12-21 15:57:46
Great problem! Last edit: 2020-12-23 03:30:47 |
||||||||||||||
2020-10-06 23:00:37
BFS with queue of pairs;) |
||||||||||||||
2020-10-03 22:51:02
int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={-1,1,1,-1,2,-2,2,-2}; take help of this array for traversing, if source and destination are same print 0. |
||||||||||||||
2020-09-17 10:57:22
@tj2972001 |
||||||||||||||
2020-08-25 22:31:30
if you are getting TLE try fixing the same cell test case like : 1 a1 a1 ans: 0 |
||||||||||||||
2020-08-19 08:05:01
AC in one go. Easy path finding |
||||||||||||||
2020-08-13 13:48:17
I used BFS to solve this question. Hints for beginners: 1. Convert the start[0] and end[0] to respective integer value by use ASCII table. 2. Maintain a depth level for bfs and when the knight reaches the desired end point return the depth. |