Connection Status:
Competition Arena > RookAttack

RookAttack

TCO '03 Semifinals 4 · 2003-10-07 · by brett1479

TCO '03 Semifinals 4 · 2003-10-07 · by brett1479 · Graph Theory
Class Name: RookAttack
Return Type: int
Method Name: howMany
Arg Types: (int, int, vector<string>)
Problem Statement

Problem Statement

You have been given a rows-by-cols chessboard, with a list of squares cut out. The list of cutouts will be given in a String[] cutouts. Each element of cutouts is a comma-delimited lists of coords. Each coord has the form (quotes for clarity) "r c". If coord "r c" appears in an element of cutouts, it means that the square at row r column c (0-based) has been removed from the chessboard. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Your method will return an int that will be the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.

Constraints

  • rows will be between 1 and 300 inclusive.
  • cols will be between 1 and 300 inclusive.
  • cutouts will contain between 0 and 50 elements inclusive.
  • Each element of cutouts will contain between 3 and 50 characters inclusive.
  • Each element of cutouts will be a comma delimited list of coords. Each coord will be of the form "r c", where r and c are integers, with no extra leading zeros, r is between 0 and rows-1 inclusive, and c is between 0 and cols-1 inclusive.
  • Each element of cutouts will not contain leading or trailing spaces.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
8
8
{}
Returns: 8

In the example cases the .'s represent squares of the chessboard, and the X's represent cut out squares. ........ ........ ........ ........ ........ ........ ........ ........

1)
2
2
{"0 0","0 1","1 1","1 0"}
Returns: 0

XX XX

2)
3
3
{"0 0","1 0","1 1","2 0","2 1","2 2"}
Returns: 2

X.. XX. XXX

3)
3
3
{"0 0","1 2","2 2"}
Returns: 3

X.. ..X ..X

4)
200
200
{}
Returns: 200
5)
3
3
{"0 0","1 1","2 1"}
Returns: 3

X.. .X. .X.

6)
6
6
{"0 0","0 2","0 4",
 "1 1","1 3","1 5",
 "2 0","2 2","2 4",
 "3 1","3 3","3 5",
 "4 0","4 2","4 4",
 "5 1","5 3","5 5",
 "2 0","2 2","2 4"}
Returns: 6

X.X.X. .X.X.X X.X.X. .X.X.X X.X.X. .X.X.X

7)
4
4
{"0 0","0 1","1 2","2 0","2 1","2 0","2 1"}
Returns: 4

XX.. ..X. XX.. ....

9)
300
300
{
"149 149",
"149 151",
"151 149",
"151 151",
"148 148",
"148 152",
"152 148",
"152 152",
"147 147",
"147 153",
"153 147",
"153 153",
"146 146",
"146 154",
"154 146",
"154 154",
"145 145",
"145 155",
"155 145",
"155 155",
"144 144",
"144 156",
"156 144",
"156 156",
"143 143",
"143 157",
"157 143",
"157 157",
"142 142",
"142 158",
"158 142",
"158 158",
"141 141",
"141 159",
"159 141",
"159 159",
"140 140",
"140 160",
"160 140",
"160 160",
"139 139",
"139 161",
"161 139",
"161 161",
"138 138",
"138 162",
"162 138",
"162 162",
"137 137",
"137 163"}
Returns: 300

The cutouts form a large "X" in the middle.

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

Coding Area

Language: C++17 · define a public class RookAttack with a public method int howMany(int rows, int cols, vector<string> cutouts) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous