matriz de una moneda de transferencia algoritmo a otra matriz de moneda

Question

Descripción:
Hay $mn$ ($m \leq 100$, $n \leq 100$) monedas en el escritorio formando un $m\times n$ moneda de la matriz. Cada moneda en la cara arriba o cara hacia atrás, representados por 0 o por 1.

Las reglas del juego son:

(1) cada vez, se le permite a la inversa una fila de monedas.
(2) cada vez, se le permite intercambiar dos columnas.

Objeto:
a partir de la matriz inicial -> destino de la matriz

Entrada:
1. $k$ el recuento de caso de prueba
2. $m n$ el recuento de filas y columnas
3. los números de la matriz inicial y el destino de la matriz

Salida los menos pasos desde la fase inicial de la matriz de objetivo de la matriz, si no es posible la transferencia de la inicial de blanco, la salida de -1.

muestra de la potencia

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

ejemplo de salida

2

-1

Yo he programado una solución: mysolution.ccque enumerar todas las posibilidades y lo que es correcto, pero es demasiado lento, podría proporcionar una correcta pero rápida solución.

Gracias.

Answer 1

Tenga en cuenta que si usted invierte una fila o no es independiente de la columna de swaps y operaciones de otras filas: se determina por el número de ceros y unos en la fila, y en la fila correspondiente de la meta de la matriz.

Así, una vez que determine que las filas de a la inversa, ahora se ha quedado con la determinación de si las columnas de la matriz inicial son una permutación de la meta de la matriz.

Con el fin de obtener el mínimo número de intercambios, creo (no lo he probado probarlo) si descomponer la permutación en ciclos, y de intercambio de columnas a lo largo del ciclo, usted recibirá su respuesta.

(Usted puede optimizar la última parte por el tratamiento de cada columna como un 100 número de bits, y el uso de tablas hash, etc).

Answer 2

Observe las siguientes:

1. La inversión y el intercambio de conmutar. Por lo tanto, si no hay una solución, siempre se puede encontrar uno que tiene todas las inversiones antes de que todos los swappings.

2. Una solución sólo existe si el número de cabezas en cada fila se puede lograr mediante la inversión.

3. La decisión de si una fila se debe invertir o no es trivial si $m$ es impar o $m$ es regular y el número de cabezas $\neq m/2$. Vamos a llamar a esas filas trivial.

Ahora, si sólo hay trivial filas, usted sólo tiene que encontrar el óptimo de intercambio. Este problema ha sido discutido en StackOverflow ya. (El hecho de que los objetos son vectores de longitud $n$ no cambia el problema en principio. Sin embargo, si usted requiere que sólo las columnas adyacentes se intercambian, se hace referencia solución no es directamente aplicable, como las columnas no tienen que ser únicos.)

El problema se vuelve muy interesante, si hay sólo no trivial filas, así que vamos a centrarnos en este caso.

Suponga $m$ incluso, y todas las filas que contienen exactamente $m/2$ cabezas. El algoritmo es como sigue:

• Para todas las columnas $j$

  • Para todas las filas $i$

    • Invertir fila $i$, de modo que su $j$-ésima columna coincide con la primera columna de la meta de la matriz

  • Trate de encontrar una solución utilizando swaps sólo (ver arriba caso trivial)

• Recoger la columna de $j$ para que el número de intercambios requerido es mínimo

Los supuestos no son utilizados en el algoritmo a todos, va a trabajar para triviales y mezclado de los casos, demasiado. Usted puede optimizar para el trivial y el mezclado de los casos, sin embargo.