The algorithm transfers one coin matrix to another coin matrix

Question

Description:
On the desktop there are coins m * n (m <= 100, n <= 100), which form the matrix of the coin m row n. Each coin is either facing up or facing back, indicated by 0 or 1.

Rules of the game:

(1) Each time you are allowed to invert one row of coins.
(2) every time, you can swap two columns.

An object:
from source matrix → target matrix

Input:
1. k - test test counter 2. mn number of rows and columns
3. inital matrix and target matrix numbers

The output is the smallest steps from the source matrix to the target matrix, if it is impossible to transfer from the initial to the target, the output is -1.

sample intput

2
4 3
1 0 1
0 0 0
1 1 0
1 0 1

1 0 1
1 1 1
0 1 1
1 0 1

4 3
1 0 1
0 0 0
one hundred
1 1 1

1 1 0
1 1 1
0 1 1
1 0 1

sample output

2

1

I encoded one solution: mysolution.cc , which lists all the features and what's right, but it's too slow, you could provide the right, but quick solution.

Thanks.

Answer 1

Rows always remain in the same place, so if a line r starts with k , it will always be either k , or columns - k .

• for each row, check if count_of_ones(initial,row) == count_of_ones(target,row) , if yes, fine, also check if count_of_ones(initial,row) = columns - count_of_ones(target,row) , if so , flip row, else output -1 . As @maniek noted, it’s not so easy when exactly half the columns contain them. Such rows should be processed in step 2 in order to try to form the necessary columns.
• for each column, count the number of units of int target and the working matrix (after turning over the rows as needed). If the sequence of samples are not permutations of each other, output -1 , otherwise try to find a permutation of the columns that convert the work to the target (any columns that are identical between the working and the target should be kept fixed). If this is not possible, print -1 , otherwise find the minimum number of swaps required to achieve this permutation.

Answer 2

I will give you some thoughts. You compare line by line. If the ith row of the first matrix has the same number 1 as in the ith row of the second matrix, then you are not inverting. If the ith row of the first matrix has the same number 1 as 0 in the ith row of the second matrix, then you must invert. If none of them is true, then there is no solution. It is all about the opposite.

Now all the columns are equal, but in a different order (the second matrix has permutation columns from the first matrix). If the columns are not rearranged, return -1. This problem is equal to the minimum number of swaps to convert one permutation to another.