Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
This question already has an answer here:
You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.
I can only think of a bfs solution. Is there a better solution possible?
The question is further extended by adding obstacles to the board. How to solve this question what will be the complexity.(I basically need a answer for this.)
Thank you.
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Without obstacles you can solve this in constant time. You'll have to work the details out, but the idea is that in two moves if you want to cover distance you can move 4 steps in one direction and 0 or 2 in the either, or 3 steps in each direction. So let's say the distance is (100, 48): You do 24 double moves (4, 2) plus 1 double move (4, 0). Let's say the distance is (100, 60): You move diagonally until one distance is half the other, say 8 double moves (3, 3) leaving a distance of (76, 36) which can be covered in 19 double moves.
You make a small table of how to best cover small distances: (0, 0) takes 0 moves, (1, 0) takes three moves, (1, 1) takes two moves, (2, 0) takes two moves, (2, 1) takes 1 move, (2, 2) takes 4 moves, etc. And you are left with a small number of possibilities how to go a large distance in the fastest way, followed by a small distance.
With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.
Define the "optimal distance" between points as the distance given by the algorithm for lowest number of moves without obstacles. At the starting point, find all neighbouring points, and for each calculate a lower bound for the number of moves to the target: One initial move, and the moves for the closest distance to the target. Then the same from the other end. Next you examine those points with the lowest lower bound. All moves are eventually evaluated, bot you tend to check those first that get you closer to the target.
