Find the Minimum Moves for the knight to move from source to destination on infinite chess board

+1 vote
asked in Interview Question by rajivtyagi711
edited by admin

Given Infinite chess board, 2 coordinates are given (source, destination). Find the Minimum Moves for the knight to move from source to destination.

 

I have encountered this question twice and got rejected twice and I still don't know the solution.

When I told BFS is the solution, interviewer straight away says how much we take the visited matrix and queue since the board is infinite.

So BFS is not the solution,

Please tell the solution.

Add question to:

1 Answer

0 votes
answered by admin
edited by admin

Look at the pattern in the below image.Here number in the cell is representing minimum moves to reach that cell from center ie. (0,0).As you have infinite chess board then you can make source cell to (0,0) by shifting origin to the source.By this, your destination will also be changed. Now think about how will you generalize the below pattern :


This is symmetric for the both axis.

...