algorithm transfer one coin matrix to another coin matrix

Description:
There are $mn$ ($m \leq 100$, $n \leq 100$) coins on the desktop forming an $m\times n$ coin matrix. Every coin either face upward, or face backward, represented by 0 or 1.

Rules of the game are:

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

Object:
from initial matrix -> target matrix

Input:
1. $k$ the count of test case
2. $m n$ the count of rows and columns
3. the numbers of the initial matrix and the target matrix

Output the least steps from initial matrix to target matrix, if it is not possible to transfer from initial to target, output -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
1 0 0
1 1 1

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

sample output

2

-1

I have coded one solution: mysolution.cc, which enumerate all posibilities and which is correct but it is too slow, could you provide a correct but fast solution.

Thanks.

-
Have you thought about A* search? –  Chris Taylor Feb 3 '12 at 15:51
@Arturo Magidin: Thanks for your edit. –  Jichao Feb 3 '12 at 15:53
@Chris Taylor: I do not know what is A* search. –  Jichao Feb 4 '12 at 12:53
Unfortunately I can't link to the wikipedia article (Stack Exchange removes the * in the url) but you should be able to find it yourself. It's a general purpose search method for solving problems like this, and is guaranteed to find the minimal solution. –  Chris Taylor Feb 5 '12 at 0:17

Note that whether you reverse a row or not is independent of the column swaps and operations on other rows: it is determined by the numbers of zeroes and ones in that row, and in the corresponding row of the target matrix.

Thus once you determine which rows to reverse, you are now left with determining if the columns of initial matrix are a permutation of the target matrix.

In order to get the minimum number of swaps, I believe (haven't tried proving it) if you decompose the permutation into cycles, and swap columns along the cycle, you will get your required answer.

(You can optimize the latter part by treating each column as a 100 bit number, and using hashtables etc).

-
I didn't consider the case which user946850 calls non-trivial. So this answer is incomplete. Of course you could just enumerate all the non-trivial possibilities and apply the above. –  Aryabhata Feb 3 '12 at 22:52
+1 for "decomposition into cycles" :-) –  krlmlr Feb 3 '12 at 23:19

Observe the following:

1. Inversion and swapping commute. Hence, if there's a solution, you can always find one that has all inversions before all swappings.

2. A solution only exists if the required number of heads in each row can be achieved using inversion.

3. The decision if a row must be inverted or not is trivial if $m$ is odd or $m$ is even and the number of heads $\neq m/2$. Let's call such rows trivial.

Now, if there are only trivial rows, you only have to find the optimal swapping. This problem has been discussed on StackOverflow already. (The fact that the objects are vectors of length $n$ doesn't change the problem in principle. However, if you require that only adjacent columns are swapped, the referenced solution is not directly applicable, as columns don't have to be unique.)

The problem becomes interesting if there are only non-trivial rows, so let's focus on this case.

Assume $m$ even, and all rows contain exactly $m/2$ heads. The algorithm goes as follows:

• For all columns $j$

• For all rows $i$

• Invert row $i$ so that its $j$-th column matches the first column of the target matrix
• Try to find a solution using swaps only (see above trivial case)

• Collect the column $j$ for which the number of swaps required is minimal

As the assumptions aren't used in the algorithm at all, it will work for trivial and mixed cases, too. You can optimize for the trivial and mixed cases, though.

-
The problem calls for the minimum number of swaps required, not just existence. +1 though. –  Aryabhata Feb 3 '12 at 22:53
Thanks, didn't notice that. Will edit. –  krlmlr Feb 3 '12 at 22:56