Anuncios de móviles
Cuando a Cayo Lograbo le propusieron grabar el anuncio para el lanzamiento del último móvil de moda, no lo dudó dos veces y aceptó. Sería una buena línea para añadir en su currúculum como cámara de televisión y cine y le daría unos ingresos que le venían de perlas.
Cuando el director de la campaña le dijo qué tipo de tomas tenía en mente, la cosa ya no le pareció tan maravillosa. Quería colocar en un campo de deportes un montón de móviles formando una cuadrícula. Teniendo algunos encendidos y otros apagados se formaría, a modo de pixel art, una imagen con el logotipo de la compañía.
Le dieron los móviles necesarios y muy poco tiempo, de modo que solo pudo cargar la batería de los que pondría encendidos para formar la imagen. Luego colocó todos en el campo, formando una inmensa matriz y pudo, por fin, grabar la toma.
Cuando estaban ya celebrando en un bar el trabajo bien hecho, vino la puntilla del director. ¡Bien! — dijo — Mañana grabamos la última, con los móviles configurados para formar un pulgar hacia arriba.
La papeleta que se encontró al día siguiente fue grande: tenía un montón de móviles colocados, algunos apagados sin batería, otros encendidos y otros colgados mostrando un mensaje de error pidiendo un reinicio. Su tarea: conseguir la imagen final lo antes posible, teniendo en cuenta que lo que podía hacer era:
- Apagar un móvil que estuviera encendido y dejarlo apagado.
- Apagar o reiniciar un móvil colgado mostrando el mensaje de error.
- Intercambiar dos móviles de posición.
¿Cuántas de esas acciones tenía que hacer como mínimo para conseguir la imagen final?
Entrada
La entrada está compuesta por distintos casos de prueba.
Cada caso de prueba comienza con una línea indicando el número de filas y de columnas (entre 1 y 100) que tiene la cuadrícula de móviles. A continuación aparecen, uno a la derecha del otro, el estado de los móviles por la mañana y el deseado para grabar la toma. En particular, habrá tantas líneas como filas tiene la cuadrícula, cada una de ellas con dos bloques de caracteres, separados por un espacio. Cada bloque está compuesto de tantas letras como columnas tiene la cuadrícula.
Los móviles apagados (y sin batería) aparecen con un 0, los encendidos con un 1 y los colgados con una R. La primera figura, a la izquierda, indica la configuración inicial y la segunda, a la derecha, la deseada. Se garantiza que en la deseada no habrá ninguna posición con una R.
La entrada termina con dos ceros.
Salida
Por cada caso de prueba se escribirá una única línea con el número mínimo de operaciones que hay que realizar para conseguir la imagen final. Si no se puede, se escribirá IMPOSIBLE.
Un móvil encendido puede apagarse, un móvil colgado puede apagarse o reiniciarse para pasar a estar encendido, y dos móviles pueden intercambiarse entre ellos. Ten en cuenta que los móviles apagados están sin batería y no pueden encenderse.
Entrada de ejemplo
2 3 000 000 111 111 2 3 100 000 011 111 2 3 00R 011 001 100 0 0
Salida de ejemplo
0 1 IMPOSIBLE