TransformMatrix | Topcoder Archive

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

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

{"011101",
 "110000",
 "000011",
 "000000",
 "100000"}

{"110100",
 "000011",
 "000000",
 "110001",
 "000010"}

{"305713",
 "537211",
 "352421",
 "242212",
 "333313"}

Returns: 10

{"10",
 "00"}

{"00",
 "01"}

{"11",
 "11"}

Returns: 1

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)2024, TopCoder, Inc. All rights reserved.