Connection Status:
Competition Arena > EllysFigurines

EllysFigurines

TCO13 Round 1B · 2013-02-19 · by espr1t

TCO13 Round 1B · 2013-02-19 · by espr1t · Brute Force, Simulation
Class Name: EllysFigurines
Return Type: int
Method Name: getMoves
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

Elly has placed several (possibly none) figurines on a rectangular board with several rows and columns. Now Kristina wants to remove all figurines from the board. In a single move she selects either up to R consecutive rows, or up to C consecutive columns and removes all remaining figurines that are located there. The girl wonders what is the minimal number of moves in which she can clear the entire board.

The position of the figurines will be given to you in the String[] board. The j-th character of the i-th element of board will be '.' if the cell is empty, or 'X' if it contains a figurine. The maximal number of cleared rows in a single move will be given in the int R. The maximal number of cleared columns in a single move will be given in the int C. Return the minimal number of moves that is sufficient to clear the entire board.

Notes

  • In a single move the girl can only select a consecutive group of rows or columns to be cleared. In other words, in each move Kristina first decides whether she wants rows or columns, then she picks the index i of the first chosen row/column, then the number k of chosen rows/columns, and finally she removes all figurines from the rows/columns with indices i, i+1, i+2, ..., i+k-1.

Constraints

  • board will contain between 1 and 15 elements, inclusive.
  • Each element of board will contain between 1 and 15 characters, inclusive.
  • All elements of board will contain the same number of characters.
  • Each character of board will be either '.' or 'X'.
  • R will be between 1 and 15, inclusive.
  • C will be between 1 and 15, inclusive.
Examples
0)
{".X.X.",
 "XX..X",
 ".XXX.",
 "...X.",
 ".X.XX"}
1
2
Returns: 3

In this case in a single move Elly can remove all figurines from a single row, all figurines from a single column or all figurines from two consecutive columns. One way to achieve the optimal answer here would be to remove the figurines from the first and second column in the first move, then the ones from the fourth and fifth column in the second move, and finally the remaining ones on the third row in the third move. Another solution would be to erase only columns, again using three moves.

1)
{".X.X.",
 "XX..X",
 ".X.X.",
 "...X.",
 ".X.XX"}
2
2
Returns: 2

Almost the same as the first example, but without the figurine in the middle and the number of maximal rows removed is increased by one. This time, the only optimal solution is to clear the first two columns in one move and the last two in another move.

2)
{"XXXXXXX"}
2
3
Returns: 1

The maximal allowed number of cleared rows or columns might be greater than the corresponding dimension of the board. The optimal solution for this board is to clear the only row in one move.

3)
{"XXXXX",
 "X....",
 "XXX..",
 "X....",
 "XXXXX"}
1
1
Returns: 4

Here clearing rows 1, 3 and 5, together with column 1 yields the best result 4.

4)
{"XXX..XXX..XXX.",
 ".X..X....X...X",
 ".X..X....X...X",
 ".X..X....X...X",
 ".X...XXX..XXX.",
 "..............",
 "...XX...XXX...",
 "....X......X..",
 "....X....XXX..",
 "....X......X..",
 "...XXX..XXX..."}
1
2
Returns: 7

Good luck in TCO 13!

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

Coding Area

Language: C++17 · define a public class EllysFigurines with a public method int getMoves(vector<string> board, int R, int C) · 197 test cases · 2 s / 256 MB per case

Submitting as anonymous