Given a chess board of order nxm and source points (s1,s2) and destination points (d1,d2), your task to find min number of moves required by the knight to go to the destination cell.
Answers
Answer:
Use Dynamic Programming Solution
Step-by-step explanation:
Use the Dynamic Programming Solution to solve this problem.
Now consider following 2 cases :-
Case 1 : If target is NOT in the same row or column of knight’s position.
Consider 8 x 8 cell chess board. Now, let assume knight is at (3, 3) and the target is at (7, 8). There are 8 moves possible from the current position of knight i.e. (2, 1); (1, 2); (4, 1); (1, 4); (5, 2); (2, 5); (5, 4); (4, 5). But, among these only two moves (5, 4) ; (4, 5) will be towards the target and all other goes away from target. So, to find minimum steps go to either (4, 5) or (5, 4). Now, calculate the minimum steps taken from (4, 5) or (5, 4) to reach the target. This can be calculated by dynamic programming. Thus, this results in the minimum steps from (3, 3) -> (7, 8).
Case 2 : If target in the same row or column of knight’s position.
Consider 8 x 8 cell chess board. Now, let’s assume knight is at (4, 3) and the target is at (4, 7). There are 8 moves possible but towards the target, there are only 4 moves i.e. (5, 5); (3, 5); (2, 4); (6, 4). As (2, 4) is equivalent to (6, 4) and (5, 5) is equivalent to (3, 5). So, from 4 points, it can be converted into 2 points. Taking (5, 5) and (6, 4). Then, calculate the minimum steps taken from these two points to reach the target. This is calculated by dynamic programming. Thus, this results in the minimum steps from (4, 3) ->(4, 7).