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).
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.
Print the minimum number of moves a knight takes to reach from start to destination in a separate line.
1 <= T <= 4096
Input: 3 a1 h8 a1 c2 h8 c3 Output: 6 1 4
@admin getting time limit exceed error in pythonLast edit: 2019-11-06 15:50:35
Wrong answer :(Last edit: 2019-10-02 19:35:49
convert (a1 h8) form to int type (11 88) using one-based indexing. then find the shortest path from 11 to 88 using bfs.
i got timelimit. why?
Nice problem just a normal bfs with direction array >>>
ac in one go(:
oh god take care of indexing it is 1-based costed me 5 WA's
good problem to learn when to apply dfs and when to apply bfs!!!
@Admin can you help me why I am getting wrong ans?