4
$\begingroup$

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.

  • 0
    Have you thought about A* search?2012-02-03
  • 0
    @Arturo Magidin: Thanks for your edit.2012-02-03
  • 0
    @Chris Taylor: I do not know what is A* search.2012-02-04
  • 0
    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.2012-02-05

2 Answers 2