TopCoder problem "TransformMatrix" used in SRM 407 (Division I Level Three)



Problem Statement

    You are given two matrices A and B. Each matrix is represented by a String[] containing only '0' and '1' digits. The j-th character of the i-th element is the value at cell (i, j). Your goal is to transform matrix A into matrix B using a series of swaps. On each swap, you choose two adjacent (horizontally, vertically or diagonally) cells in matrix A and swap their values.

There is a limit to the number of times each cell in matrix A can be used. You are given a third matrix count as a String[] containing only digits ('0'-'9'). Cell (i, j) in matrix A can be used in a maximum of count(i, j) swaps. Return the fewest number of swaps required to achieve your goal, or return -1 if it is impossible.
 

Definition

    
Class:TransformMatrix
Method:transform
Parameters:String[], String[], String[]
Returns:int
Method signature:int transform(String[] A, String[] B, String[] count)
(be sure your method is public)
    
 

Constraints

-A will contain between 1 and 20 elements, inclusive.

-A, B and count will contain the same number of elements.

-Each element of A, B and count will contain between 1 and 20 digits, inclusive.

-Each element of A, B and count will contain the same number of characters.

-Each element of count will contain only digits ('0' to '9').

-Each element of A and B will contain only '0' (zero) and '1' (one) digits.
 

Examples

0)
    
{"110", 
 "000",
 "001"}
{"000",
 "110",
 "100"}
{"222",
 "222",
 "222"}
Returns: 4
Here is one of the ways:

(0,0) - (1,1)

(0,1) - (1,0)

(2,2) - (2,1)

(2,1) - (2,0)
1)
    
{"10"}
{"01"}
{"11"}
Returns: 1
Just swap the values in the two cells of the matrix.
2)
    
{"111",
 "000",
 "111"}
{"111",
 "000",
 "111"}
{"013",
 "537",
 "136"}
Returns: 0
Matrix A is already equal to matrix B, so no swaps are required.
3)
    
{"001",
 "110"}
{"000",
 "111"}
{"000",
 "111"}
Returns: -1
Here we can't use any cell from row 0.
4)
    
{"100",
 "000"}
{"000",
 "000"}
{"999",
 "999"}
Returns: -1
The two matrices contain a different number of '1's, so it is impossible to transform one into the other.
5)
    
{"011101",
 "110000",
 "000011",
 "000000",
 "100000"}
{"110100",
 "000011",
 "000000",
 "110001",
 "000010"}
{"305713",
 "537211",
 "352421",
 "242212",
 "333313"}
Returns: 10
6)
    
{"10",
 "00"}
{"00",
 "01"}
{"11",
 "11"}
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12179&pm=9790

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Graph Theory