Connection Status:
Competition Arena > Knights

Knights

SRM 303 · 2006-05-18 · by Snail

SRM 303 · 2006-05-18 · by Snail · Graph Theory
Class Name: Knights
Return Type: int
Method Name: makeFriendly
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

There are several knights located on a NxN chessboard. Chessboard rows are numbered from 1 to N, inclusive. Chessboard columns are numbered with single characters from 'A' to 'A'+N-1, inclusive. For example, a standard 8x8 chessboard has rows 1...8 and columns A...H.

A knight is a chess piece that attacks the following squares (marked with X symbols):

If one of those squares is occupied by some other knight, those two knights are attacking each other.

An arrangement of knights is called friendly if no knight attacks another knight. Your task is to determine the minimum number of knights that can be removed to make a friendly arrangement. You will be given an int N denoting the size of the chessboard and a String[] pos containing the knight positions. Each element of pos will contain a space separated list of <COL><ROW> knight positions on the board where <COL> is the column and <ROW> is the row. Each <COL> is a letter between 'A' and 'A'+N-1, inclusive, and each <ROW> is an integer between 1 and N, inclusive, with no leading zeros. There will be no leading or trailing spaces.

Constraints

  • N will be between 1 and 26, inclusive.
  • pos will contain between 1 and 50 elements, inclusive.
  • pos will be formatted as described in the statement.
  • Each element of pos will contain between 2 and 50 characters, inclusive.
  • No two knights will occupy the same position.
Examples
0)
5
{"A2 A4", "B1 B5", "D1 D5 E2 E4 C3"}
Returns: 1

8 knights on the chessboard are attacked by knight C3, so it should be removed.

1)
2
{"A1 A2 B1 B2"}
Returns: 0

This is a 2x2 chessboard, so no knight is under attack.

2)
6
{"A1 A5 B3 C1 C5 D2 D4 E6 F5"}
Returns: 3

One possible way is to remove B3, C5 and D4.

3)
8
{"A2 A4 A5 A6 B2 B5 B6 B7 B8",
 "C3 C8 D1 D2 D3 D4 D5 D6 D8",
 "E1 E3 E8 F1 F2 F8 G3 G5 H4 H7 H8"}
Returns: 12
4)
9
{"A3 A4 A5 A7 A8 B6 B8 C3 C6",
 "C7 C9 D4 D5 D8 D9 E1 E3 E7",
 "F2 G2 G6 G7 H2 H9 I2 I4 I5",
 "I6 I7 I8 I9"}
Returns: 10

Submissions are judged against all 102 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Knights with a public method int makeFriendly(int N, vector<string> pos) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous