JOIN
Get Time

   Problem Statement  

 Problem Statement for EllysFigurines

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.
 

Definition

    
Class:EllysFigurines
Method:getMoves
Parameters:String[], int, int
Returns:int
Method signature:int getMoves(String[] board, int R, int C)
(be sure your method is public)
    
 

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!

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2013 TCO Algorithm Round 1B - Division I, Level Two