TopCoder problem "ZeroesAndOnesGrid" used in TCHS07 Finals (Division I Level Two)



Problem Statement

    

You are given a String[] table containing only zeroes and ones and describing a rectangular grid. The j-th character of the i-th element of table corresponds to the value in the i-th row and j-th column of the grid (all indices are 0-based). Return the minimal number of moves required to change all the cells in the grid to zeroes. This will always be possible.

In each move, you choose a single cell (R, C) in the grid (R-th row, C-th column). This inverts the values of all cells (r, c), where r is between 0 and R, inclusive, and c is between 0 and C, inclusive. Inverting the value of a cell means changing zero to one and vice versa.

 

Definition

    
Class:ZeroesAndOnesGrid
Method:minMovesCount
Parameters:String[]
Returns:int
Method signature:int minMovesCount(String[] table)
(be sure your method is public)
    
 

Constraints

-table will contain between 1 and 50 elements, inclusive.
-Each element of table will contain only '0' (zero) and '1' (one) characters.
-Each element of table will contain the same number of characters.
-Each element of table will contain between 1 and 50 characters, inclusive.
 

Examples

0)
    
{"0000", 
 "0000"}
Returns: 0
All the cells are already zeroes, so nothing needs to be inverted.
1)
    
{"11111", 
 "11111"}
Returns: 1
Choose the cell in the bottom right corner to invert the whole grid.
2)
    
{"01", 
 "01"}
Returns: 2
3)
    
{"00", 
 "01"}
Returns: 4
4)
    
{"010101011010000101010101"}
Returns: 20

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10764&pm=7806

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Greedy