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).

knight

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
aryanchauhan_0: 2021-08-24 22:50:07

feel great after solving this problem

Waseem Ahmed: 2021-06-10 13:53:43

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

crawler_123: 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}}

sanchit2812: 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.

swarna1214: 2021-04-01 08:42:29

Why am I getting WA? My code seems to give right answers. Please help me.

swarna1214: 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
om_37: 2021-02-05 14:38:50

AC in one go..very nice problem for learning

tinedis740: 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

sma5nico: 2020-12-21 15:57:46

Great problem!

Last edit: 2020-12-23 03:30:47
tarun_28: 2020-10-06 23:00:37

BFS with queue of pairs;)


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