TopCoder problem "MatrixTransforming" used in SRM 311 (Division I Level One , Division II Level Three)



Problem Statement

    Given two matrices a and b, both composed of zeroes and ones, return the minimal number of operations necessary to transform matrix a into matrix b. An operation consists of flipping (one becomes zero and zero becomes one) all elements of some contiguous 3 x 3 submatrix. If a cannot be transformed into b, return -1.
 

Definition

    
Class:MatrixTransforming
Method:minPushes
Parameters:String[], String[]
Returns:int
Method signature:int minPushes(String[] a, String[] b)
(be sure your method is public)
    
 

Constraints

-a will contain between 1 and 50 elements, inclusive.
-a and b will contain the same number of elements.
-Each element of a will contain between 1 and 50 characters, inclusive.
-Each element of b will contain between 1 and 50 characters, inclusive.
-All elements of a and b will contain the same number of characters.
-Each element of a and b will be contain only zeroes ('0') and ones ('1').
 

Examples

0)
    
{"111","111","111"}
{"000","000","000"}
Returns: 1
Flip the entire 3 x 3 matrix.
1)
    
{"1"}
{"0"}
Returns: -1
No flip can be made here.
2)
    
{"001","100","100","000","011","010","100","100","010",
"010","010","110","101","101","000","110","000","110"}
{"001","100","011","000","100","010","011","100","101",
"101","010","001","010","010","111","110","111","001"}
Returns: 7
3)
    
{
"0000",
"0010",
"0000"
}
{
"1001",
"1011",
"1001"
}
Returns: 2
Flip each of the two 3 x 3 submatrices once.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9991&pm=6431

Writer:

gevak

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Greedy