Given an integer N and knight position {x, y}, the task is to print all possible sets of points that the knight can reach in one move on an N*N chessboard.
Note: Output the points in sorted order.
Examples:
Input: N = 4, x = 2, y = 2
Output:
(0, 1)
(0, 3)
(1, 0)
(3, 0)
Explanation: Knight can be moved from (2, 2) to (0, 1), (0, 3), (1, 0) and (3, 0).Input: N = 5, x = 3, y = 3
Output:
(1, 2)
(1, 4)
(2, 1)
(4, 1)
Explanation: Knight can be moved from (3, 3) to (1, 2), (1, 4), (2, 1), (4, 1).
Approach: To solve the problem follow the below idea:
The idea is to find all the possible moves of a knight on a chessboard. Store the possible horizontal and vertical moves in two arrays and add these values to the current position and check if the new position is inside the board, add this new position to the resultant vector. Now, sort the vector in ascending order and return it.
Below are the steps involved in the implementation of the code:
- Create two arrays of possible movements dx[] and dy[] which hold the row and column movements a knight can make. We initialize these with all possible knight moves.
- We create an empty vector say moves to store all the possible moves the knight can make.
- Iterate the dx and dy arrays to compute the new position of the knight.
- newX = x + dx[i], newY = y + dy[i]
- Now check if the new position is valid (i.e. within the boundaries of the chessboard of size n), and add it to the moves vector.
- After all possible moves have been checked, sort the moves vector in lexicographic order.
- Iterate the moves vector and print each possible move in lexicographic order.
Below is the implementation of the above approach:
C++
|
(0, 1) (0, 3) (1, 0) (3, 0)
Time Complexity: O(1)
Auxiliary Space: O(1)