Cisco OA-11 2023

Problem Description

Mandy's elder brother Rob is a chess prodigy. Mandy challenges Rob to a chess problem on a standard 8*8 board:

• A knight is placed at the coordinates X.
• There are M pawns placed at coordinates Y[i] (i = 1 to M).

Task: Determine the minimum number of moves the knight needs to kill all M pawns. A knight moves in an "L" shape: 2 horizontal and 1 vertical or 2 vertical and 1 horizontal.

Input Format:

• The first line contains the number of pawns, M.
• Next M lines contain the coordinates of the pawns.
• The next line contains the coordinates of the knight.

Output Format:

• Output the minimum number of moves required to kill all the pawns.
• If it's impossible to kill all pawns, the output -1.

Constraints: The maximum value of M can be 8

Test Case Example

Sample Input:

2
1 2
2 4
1
0 0

Sample Output:

2

Sample Explanation:

• There are 2 pawns:
  • P1 at coordinates (1, 2)
  • P2 at coordinates (2, 4)
• The knight starts at (0, 0).
• The best strategy is:
  1. Move to capture P1 in the first move.
  2. Move to capture P2 in the second move.
• Total moves: 2.