Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### TooWeak_TooSlow's blog

By TooWeak_TooSlow, history, 3 months ago, ,

Hello Everyone, I am trying to solve this problem. but not able to come up with a solution. can someone help me with solving the problem any approach/hint.

Problem Statement: Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position. Only Perpendicular Moves Are Allowed.

Constraints:

1<=N<=150. 0<=StartX<=64 0<=StartY<=64

0<=EndX<=64 0<=EndY<=64

StartX and StartY Indicate Starting Location. EndX and Endy Indicate Ending Location.

Test Case:

Input:

N=8 startX and StartY = 0,5

endX and endY = 6,5

output: 3

 » 3 months ago, # |   0 Auto comment: topic has been updated by TooWeak_TooSlow (previous revision, new revision, compare).
 » 3 months ago, # |   +5 How is the output 3?
•  » » 3 months ago, # ^ |   0 I don't remember correctly.sorry for inconvenience.
 » 3 months ago, # |   0 Looks like straightforward bfs
•  » » 3 months ago, # ^ |   0 But straightforward forward bfs check for X+1 and y+1 moves.
•  » » » 3 months ago, # ^ |   0 Not sure I understand. What are perpendicular moves?
•  » » » » 3 months ago, # ^ |   0 Moves: X+1 and y+2 Or X+2 and y+1
•  » » » » » 3 months ago, # ^ |   0 Then bfs will work easily, where are you having trouble?Consider each cell as a node in the graph, and add an edge if we can reach from one node to another using whatever move, then do bfs
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I am not able to implement the approach/solutionWhat if the while searching/checking for valid configuration it goes out of the graph/grid. Can you help me out. It similar to this problem:https://www.codechef.com/problems/FIN03
•  » » » » » » » 3 months ago, # ^ |   0 It's a simple if condition to check while adding edges in the graph, it will never go out
•  » » » » » » » » 3 months ago, # ^ |   0 Okay. Can you share code if possible.
•  » » » » » » » » » 3 months ago, # ^ |   0 Here's a code for 8x8 board, just generalize it to nxnhttp://competitiveprogrammer.blogspot.com/2015/04/spojnakanjminimum-knight-moves.html
•  » » » » » » » » » 3 months ago, # ^ |   0 Okay. Thanks For help.
 » 3 months ago, # |   0 Represent the grid as a graph and do a breadth first search from the starting point.
•  » » 3 months ago, # ^ |   -6 But moves are prependucilar so simple bfs algorithm will work? Can you explain briefly if possible.
•  » » » 3 months ago, # ^ |   0 I think n00bie has already explained the approach. Regarding what to do to avoid out of bounds. Assume I am at point (i,j) and want to add edges. I want to add edges from (i,j) to (i+1, j+2), (i+2,j+1), (i-1,j-2) and (i-2,j-1). Before I add each of these edges I check to see the destination point is in the grid. If is it not I don't add the edge.
•  » » » » 3 months ago, # ^ |   0 Okay. Thanks For help.