|
|
2295 - Double Vision |
||||
|
|
|||||
La compañía Doble Visión diseña tintas y fundiciones que fácilmente pueden ser leídos por humanos y máquinas. Ellos diseñan sus fundiciones en una reja rectangular. Mostrados abajo en un diseño muy simple de 5 x 3 para los primeros cinco dígitos.
.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o
La tinta aparece para ser tinta negra normal pero debajo de la superficie Doble Visión se agrega una especial polímero que puede ser detectado por un “Scanner” infrarrojo. Un humano ve la tinta negra pero no el polímero, y una máquina ve el polímetro, pero no la tinta negra. El único problema es que el polímero es más caro que la tinta, entonces Doble Visión quiere que uses tan poco como sea posible. Ellos han descubierto que con muchas fundiciones, cada símbolo puede identificado únicamente por más de dos píxeles. Pero sólo agregando el polímero para uno o dos píxeles por símbolo. Drásticamente bajaron los costos mientras aún resulten 100% precisos en sus scanners. La fundición mostrada arriba tiene su propiedad; los píxeles identifican únicamente que cada letra sea destacada con ‘#’ (Hay otras opciones que funcionarían muy bien).
.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o
Tú trabajo es escribir un programa que determine es una fundición dada tiene su propiedad y si también destacan los píxeles.
La entrada consiste en una o mas pruebas, seguidas por una línea que contenga '0 0 0' (tres ceros) que señalan el final de la entrada. Cada prueba comienza con una línea que contenga tres números enteros positivo n, r, y c, separados por un espacio: n es el número de símbolos en la fundición, r es el número de fila en cada reja, y c es el número de columnas en cada reja. Las próximas líneas r contienen la imagen de cada símbolo, usando el formato exacto mostrado en los ejemplos un punto '.’. Representan una parte vacía de la reja, un minúsculo 'o' representa un píxel y las rejas adyacentes están separadas por un espacio. La total amplitud de cada línea estará a más de 79 caracteres (sin contar los caracteres del final de- la –línea), y t estará a más de 10. Las pruebas están implícitamente numeradas comenzando con 1.
Para la prueba i, la primera línea de salida dice que 'Prueba i'.Entonces determina si cada símbolo puede ser identificado únicamente con un o dos píxeles, si no la salida de una línea con la palabra ‘imposible’. De otro modo, la salida de la fundición en el mismo formato excepto la identificación de píxeles para cada símbolo esta reemplazado con '#'.
En general puede haber muchos píxeles diferentes o pares de píxeles que identifican únicamente a un símbolo. Para asegurar que la salida es única, agregamos que la siguiente definición y reglas. Cuando comparando dos píxeles, el píxel más alto – más izquierdo es el único más cercano a la cima de la reja. Si ambos píxeles están en la misma fila, entonces el más alto-mas izquierdo es el único más cercano a la izquierda de la reja.
Si un píxel funcionará, destaca el píxel más alto – más izquierdo que funcione. Nunca destacará una solución de dos – píxeles si una solución de un píxel es posible. Si dos píxeles son necesitados, destaca el par con el píxel más alto- más izquierdo. Si dos o más pares tienen el mismo píxel más alto-más izquierdo, destaca el único con el otro píxel más alto – mas izquierdo.
Sample Input
3 2 2
oo oo .o
o. .o o.
3 2 2
oo oo .o
o. .o oo
5 5 3
.o. .o. oo. oo. o.o
o.o .o. ..o ..o o.o
o.o .o. .o. oo. ooo
o.o .o. o.. ..o ..o
.o. .o. ooo oo. ..o
1 2 4
.o..
...o
0 0 0
Sample Output
Test 1impossibleTest 2#o #o .o#. .# ##
Test 3
.#. .o. #o. oo. o.#
#.o .#. ..o ..o o.o
o.o .o. .o. #o. ooo
o.o .o. #.. ..o ..o
.o. .o. ooo #o. ..o
Test 4
.#..
...o
Traducido por: Heiner Paredes Cardoso