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

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.

Constraints

1 <= T <= 4096

Example

Input:
3
a1 h8
a1 c2
h8 c3

Output:
6
1
4

hide comments
shubhamnitt: 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.

fighter_17: 2020-09-17 10:57:22

@tj2972001

omar101: 2020-08-25 22:31:30

if you are getting TLE try fixing the same cell test case like :
1
a1 a1
ans: 0

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

khoaph: 2020-05-14 17:19:09

As @ihg_2_26 noticed, be aware of case where start and destination are the same. It cost me 2 wa.

sandy_912: 2019-11-06 15:40:50

@admin getting time limit exceed error in python

Last edit: 2019-11-06 15:50:35
jemmy_neutron: 2019-10-02 06:07:07

Wrong answer :(

Last edit: 2019-10-02 19:35:49
shikhar_may7: 2019-09-25 13:42:47

convert (a1 h8) form to int type (11 88) using one-based indexing. then find the shortest path from 11 to 88 using bfs.

huyss125634: 2019-08-21 14:06:36

i got timelimit. why?

ashik_01: 2019-08-01 08:17:07

Nice Problem


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