Minimum steps to reach target by a Knight
You have been given a square chessboard of size ‘N x N’. The position coordinates of the Knight and the position coordinates of the target are also given.

Your task is to find out the minimum steps a Knight will take to reach the target position.

Example:

knightPosition: {3,4} targetPosition: {2,1}

The knight can move from position (3,4) to positions (1,3), (2,2) and (4,2). Position (4,2) is selected and the ‘stepCount’ becomes 1. From position (4,2), the knight can directly jump to the position (2,1) which is the target point and ‘stepCount’ becomes 2 which is the final answer.

Note:

1. The coordinates are 1 indexed. So, the bottom left square is (1,1) and the top right square is (N, N). 2. The knight can make 8 possible moves as given in figure 1. 3. A Knight moves 2 squares in one direction and 1 square in the perpendicular direction (or vice-versa).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘3*T’ lines represent the ‘T’ test cases. The first line of each test case contains a pair of integers denoting the initial position of the knight. The second line of each input contains a pair of integers denoting the target position. The third line of each test case contains an integer ‘N’ denoting the rows/columns of the chessboard.

Output format:

For each test case, print an integer representing the minimum steps a Knight will take to reach the target position.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints

1

Question

Minimum steps to reach target by a Knight

You have been given a square chessboard of size ‘N x N’. The position coordinates of the Knight and the position coordinates of the target are also given.

Your task is to find out the minimum steps a Knight will take to reach the target position.

alt text

Example:

knightPosition: {3,4}
targetPosition: {2,1}

alt text

The knight can move from position (3,4) to positions (1,3), (2,2) and (4,2). Position (4,2) is selected and the ‘stepCount’ becomes 1. From position (4,2), the knight can directly jump to the position (2,1) which is the target point and ‘stepCount’ becomes 2 which is the final answer.

Note:

1. The coordinates are 1 indexed. So, the bottom left square is (1,1) and the top right square is (N, N).

2. The knight can make 8 possible moves as given in figure 1.

3. A Knight moves 2 squares in one direction and 1 square in the perpendicular direction (or vice-versa).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘3*T’ lines represent the ‘T’ test cases.

The first line of each test case contains a pair of integers denoting the initial position of the knight.

The second line of each input contains a pair of integers denoting the target position.

The third line of each test case contains an integer ‘N’ denoting the rows/columns of the chessboard.

Output format:

For each test case, print an integer representing the minimum steps a Knight will take to reach the target position.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 10
1 <= N <= 1000
1 <= KNIGHTPOSITION(X, Y), TARGETPOSITION(X, Y) <= N

Time limit: 1 second

Accepted Answer

Using BFS

The idea is to perform BFS traversal. Start from the initial position of the Knight and proceed to further cells. Traversal is performed using a queue. The queue stores the different paths travelled by the knight and also keeps storing the count of steps. When the target is popped from the queue, the corresponding count of the steps is the answer.

Define a class with the following data members
a. ‘X_COORDINATE’ denoting the x-coordinate
b. ‘Y_COORDINNATE’ denoting the y-coordinate
c. ‘STEP_COUNT’ denoting the number of steps.
Take two arrays ‘DIRECTION_X’ and ‘DIRECTION_Y’ storing the direction in which the knight can move.
Create a queue to store the class objects.
Take a visited array to mark the cells already visited and initialize it to false.
Push the initial position of the knight to the queue and mark it as visited.
Loop till the queue is not empty.
Pop the front element.
a. If the current cell is equal to the target cell, return the 'STEP_COUNT’ which is the minimum step a Knight will take to reach the target position.
b. Else, loop for all the reachable coordinates. If the coordinate is not yet visited and is reachable, push it to the queue along with the incremented value of ‘STEP_COUNT’.

Space Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of rows/columns.

In the worst case, all nodes will be stored in the queue.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of rows/columns.

In the worst case, all the cells will be visited.

Accepted Answer

Using DP

Let us consider various cases:

1. If the position of the knight and the target cell are along different rows and columns, that is, ‘KNIGHT_X’ is not equal to ‘TARGET_X’ and ‘KNIGHT_Y’ is not equal to ‘TARGET_Y’.

Example:

(KNIGHT_X, KNIGHT_Y)={3,3} and (TARGET_X, TARGET_Y)={6,6}

There are 8 possible moves but only 2 steps move towards the target, which are {4,5} and {5,4}.

So, using dynamic programming, minSteps[(3,3) to (6,6)] = 1+ minSteps[(4,5) to (6,6)] or minSteps[(5,4) to (6,6)].

2. If the position of the knight and the target cell are along the same rows or columns, that is, ‘KNIGHT_X’ is equal to ‘TARGET_X’ or ‘KNIGHT_Y’ is equal to ‘TARGET_Y’.

Example:

(KNIGHT_X, KNIGHT_Y)={2,4} and (TARGET_X, TARGET_Y)={6,4}

There are in total 4 steps moving towards the target which are (4,3),(4,5),(3,6),(3,2).

However, (4,3) and (4,5) are equivalent as they are equally away from the target. Similarly, (3,6) and (3,2) are equivalent.

So, using dynamic programming, ‘MIN_STEPS’[(2,4) to (7,4)] = 1+ 'MIN_STEPS'[(4,5) to (6,4)] or 'MIN_STEPS'(3,6) to (6,4)].

3. If either the knight or the target is at the corner and [abs(KNIGHT_X - TARGET_X), abs(knightY-targetY)]=[1,1], minimum steps to reach the target will be 4.

Algorithm:

Initialize a ‘DP’ array to store the subpaths to -1.
We’ll have the following base cases:
DP[a][b] where ‘a’ and ‘b’ is the difference between ‘KNIGHT_X’ and ‘TARGET_X’ and ‘KNIGHT_Y’ and ‘KNIGHT_Y’ respectively.
DP[1][0] = 3, DP[0][1] = 3, DP[1][1] = 2, DP[2][0] = 2, DP[0][2] =2, DP[2][1] =1, DP[1][2] =1.
Add all base cases which satisfies the case 3 given above.
If the target is reached by the knight, return 0.
If the cell is revisited, return the stored answer in the ‘DP’ array.
Else, select the coordinates which satisfy cases 1 and 2 given above.
Store 1 plus a minimum of the paths obtained by two coordinates in the ‘DP’ array and recur till the target is not reached.
Exchanging the coordinates x with y of both knight and target will result in the same answer. So, we’ll update the ‘DP’ array accordingly.
Return DP[ abs(KNIGHT_X - TARGET_X)] [ abs(KNIGNT_Y - TARGET_Y)] as the minimum steps a Knight will take to reach the target position.

Space Complexity: OtherExplanation:

O(abs( KX - TX ) * ( KY - TY ) ), where ‘KX’ denotes x-coordinate of knight, ‘TX’ denotes x-coordinate of the target, ‘KY’ denotes y-coordinate of the knight and ‘TY’ denotes y-coordinate of the target.

A ‘DP’ array is used to store the subpaths within the submatrix formed by the starting and destination cell.

Time Complexity: OtherExplanation:

O(abs( KX - TX ) * ( KY - TY ) ), where ‘KX’ denotes x-coordinate of the knight, ‘TX’ denotes x-coordinate of the target, ‘KY’ denotes y-coordinate of the knight and ‘TY’ denotes y-coordinate of the target.

We are dealing with the cells which come in the submatrix formed by the starting and destination cell.

You have been given a square chessboard of size ‘N x N’. The position coordinates of the Knight and the position coordinates of the target are also given.

Your task is to find out the minimum steps a Knight will take to reach the target position.

Example:

Note:

Input format:

Output format:

Note :

Constraints

Top Cognizant GenC Next interview questions & answers

Top HR questions asked in Cognizant GenC Next