LCC '21 Contest 4 J2 - Knights

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type

In the game of chess, the knight is known for being able to maneuver tricky spaces - but only in an 'L' shape. In order to further your understanding of chess and the knight, you are tasked with finding out the optimal move for a knight 1 move ahead. More formally, a knight is able to move 2 spaces in one direction and 1 space in a direction perpendicular to the first. If the space it ultimately lands on contains an enemy piece, the knight can capture it. Your goal is to find, of all pieces it can capture in one move, the one with the highest value.

Input Specification

The first line will contain two integers, 1\le X\le 8 and 1\le Y\le 8, the x and y coordinates of the knight.

The next line will contain an integer 1\le N\le 63, the number of enemy pieces.

The next N lines will contain 3 integers, 1\le x_i\le 8, 1\le y_i\le 8, 1\le p_i\le 100, the x and y coordinates of the enemy piece, and the number of points they are worth. All pieces are guaranteed to be at different positions.

Output Specification

If the knight cannot capture any piece, print out -1.

Otherwise, print out the x and y coordinates of the piece that the knight should capture - that is, the one with the highest point value. If multiple pieces have the same highest point value, print out the one that appeared earliest in the input.

Sample Input

3 5
1 6 3
5 4 4
1 1 100

Sample Output

5 4

Sample Explanation

The knight can reach (1, 6) and (5, 4), but not (1, 1); capturing the piece of (5, 4) gives the knight 4 points, which is the most that it can get.


There are no comments at the moment.