Minimum steps taken by knight to reach target

Moderate
0/80
0 upvote
Asked in companies
MicrosoftBNY MellonIQVIA

Problem statement

You are given a 2D matrix of size N x N which is nothing but a square chessboard. Given the starting and target positions of the knight, you are supposed to return the minimum number of steps required by the knight to reach the target position from the given starting point.

Note : 
Following is the possible movements of the knight from a particular position.

alt text

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
 The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.

 The first line of each test case contains one integer ‘N’ representing the side of the square chessboard or 2D matrix.

 The second line contains two integers ‘SX’ and ‘SY’ representing the starting position of the knight in the chessboard.

 The third line contains two integers ‘TX’ and ‘TY’ representing the target position in the chessboard.
Output Format : 
For each test case, return the minimum number of steps taken by the knight to reach the target position from the given starting position.
Note : 
You do not need to print anything; It has already been taken care of.
Constraints : 
1 ≤ T ≤ 50
1 ≤ N ≤ 100
1 ≤ SX,SY,TX,TY ≤ 100

Where ‘T’ is the number of test cases.
‘N’ is the side of the given chessboard or matrix.
‘SX’, ‘SY’, ‘TX’, ‘TY’ denotes the starting and target positions in the given chessboard.

Time Limit: 1 sec
Sample Input 1 :
2
10
2 3 5 9 
10
1 5 9 8
Sample Output 1 :
3
5
Explanation of Input 1 :
For, first test case, the minimum number of steps taken by the knight to reach the target position is 3.
The steps followed will be starting from (2,3) -> (3,5) -> (4,7) -> (5,9), so in total there are 3 minimum steps that a knight needs to reach target position.

For, second test case, the minimum number of steps taken by the knight to reach the target position is 5.
Sample Input 2 :
2
4
1 2 3 4
4
2 3 4 4
Sample Output 2 :
4
1
Hint

Try to think of all the possible 8 positions where the knight can reach from the current position.

Approaches (2)
Breadth-First Search

Our intuition is to think of all the positions knight can reach from the current position. This problem can be seen as the shortest path in an unweighted graph. Hence, we use BFS to solve this problem. 

A knight can move to 8 positions from (x,y). 

(x, y) -> 

    (x + 2, y + 1)  

    (x + 2, y - 1)

    (x - 2, y + 1)

    (x - 2, y - 1)

    (x + 1, y + 2)

    (x + 1, y - 2)

    (x - 1, y + 2)

    (x - 1, y - 2)

(x,y) will have an edge to the 8 neighbors defined above. 

 

Steps are as follows :

 

  1. Try all 8 possible positions where a Knight can reach from its position.
  2. If a reachable position is not already visited and is inside the board, we push this state into the queue with a distance of 1 more than its parent state.
  3. Finally, we return the distance of the target position, when it gets pop out from the queue.

 

This approach considers the implementation of Breadth-First Search for searching through cells, where each cell contains its coordinate and distance from the starting node.

Time Complexity

O(N^2), where ‘N’ denotes the side of the chessboard.

 

In the worst-case, our approach visits each element of the given chessboard, so the overall time complexity will be O(N^2).

Space Complexity

O(N^2), where ‘N’ denotes the side of the chessboard.

 

The positions are stored in a queue and since we are using a 2D array to check if a certain cell is visited or not, so the overall space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Minimum steps taken by knight to reach target
Full screen
Console