TopCoder problem "Knights" used in SRM 303 (Division I Level Two)



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.

 

Definition

    
Class:Knights
Method:makeFriendly
Parameters:int, String[]
Returns:int
Method signature:int makeFriendly(int N, String[] pos)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6070

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9824&pm=6070

Writer:

Snail

Testers:

PabloGilberto , brett1479 , Yarin , vorthys , Olexiy

Problem categories:

Graph Theory