TransformMatrix

SRM 407 · 2008-06-26 · by Gluk

SRM 407 · 2008-06-26 · by Gluk · Graph Theory

Show categories

Class Name: TransformMatrix

Return Type: int

Method Name: transform

Arg Types: (vector<string>, vector<string>, vector<string>)

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

{"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)

{"10"}
{"01"}
{"11"}
Returns: 1

Just swap the values in the two cells of the matrix.

{"111",
 "000",
 "111"}
{"111",
 "000",
 "111"}
{"013",
 "537",
 "136"}
Returns: 0

Matrix A is already equal to matrix B, so no swaps are required.

{"001",
 "110"}
{"000",
 "111"}
{"000",
 "111"}
Returns: -1

Here we can't use any cell from row 0.

{"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.

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

Coding Area

Language: C++17 · define a public class TransformMatrix with a public method int transform(vector<string> A, vector<string> B, vector<string> count) · 152 test cases · 2 s / 256 MB per case