|
|
2998 - Merging Maps |
||||
|
|
|
||||
Las imágenes tomadas desde un avión o un satélite de un área cartografiada a menudo son de alta resolución para identificar de forma exclusiva características principales. Desde una sola imagen puede cubrir sólo una pequeña porción de la tierra, cartografiar zonas más amplias requiere la toma de fotografías de áreas más pequeñas superpuestas y, a continuación, se fusionan estos para producir un mapa de un área más grande.
Para este problema se le da varios mapas de áreas rectangulares, cada uno representado como una matriz de celdas de caracteres únicos. Una celda contiene un carácter alfabético en mayúsculas (“A” a “Z”), si su área correspondiente contiene una característica importante de identificación. Diferentes letras corresponden a las diferentes características, pero la misma característica importante (como un camino) puede ser identificada en varias celdas. Una celda contiene un guión (“-“) si no tiene características de identificación ubicado en el área celda. La fusión de dos mapas superpuestos nos dicen que una o más características comunes principales han sido alineadas. Una celda que contiene una característica principal en un mapa puede estar superpuesta con una celda que no contiene una característica principal en el otro. Sin embargo, las diferentes características principales (con diferentes letras) no pueden ser superpuestas en la misma celda.
--A-C C---- C---- ----D -D--C
----D D---F ----- -E--B ----G
----B B---- B-A-C ----- ----B
Map # 1 2 3 4 5
Considerar los cinco 3-filas, 5-columnas de los mapas que se muestran arriba. La columna del extremo derecho del mapa 1 combina perfectamente con la columna de la izquierda el mapa 2, por lo que los mapas pueden ser superpuestos para obtener una 3-fila, 9-columna del mapa. Pero el mapa 1 podría también superponerse con el mapa 3, ya que las características de C y B en la columna derecha del mapa 1 coinciden con los de la columna izquierda de mapa 3, la D no coinciden perfectamente por el “-“ en el centro de la columna, pero no hay conflicto. De manera similar, la fila superior del mapa 1 podría también superponerse con la fila de abajo del mapa 3.
El “resultado” de un par de mapas indica el rango en que los dos mapas están unidos.
El resultado de una superposición de una par de mapas, es el número de células conteniendo las principales características que coinciden en la superposición, indicando la mejor unión.
La puntuación del par de mapas es la puntuación máxima para la posible superposición de los mapas. Por lo tanto, la puntuación por un par de mapas de cada uno teniendo 3 filas y 5 columnas debe estar en el rango de 0 a 15.
Un “desplazamiento” es un par de enteros (r, c), que especifica cómo dos mapas, a y b, se superponen. El valor de r da al desplazamiento de filas de b en relación a las filas en a; similarmente, c da el desplazamiento de las columnas en b en relación con las columnas a.
Por ejemplo, la superposición de mapa 1 y mapa 2 que se muestran arriba tiene un desplazamiento de (0,4) y un puntaje de 3. Los dos superposiciones de mapa 1 y mapa 3 dieron resultados de tener 2 desplazamientos de (0,4) y (-2,0).
Los pasos siguientes describen cómo combinar una secuencia de mapas:
1. Fusionar el par de mapas de la
secuencia que produce el mayor resultado positivo (vincular la solución
resultante del par elegido, esta tiene los mapas con el menor número de
secuencia).
2. Eliminar los mapas que se fusionaron con la secuencia.
3. Agregar el mapa fusionado resultante a la secuencia, dándole al siguiente
mayor número de secuencia.
En el ejemplo anterior, los mapas 1 y 2 se fusionaron para producir el mapa 6, y los mapas 1 y 2 se eliminaron de la secuencia. Los pasos 1, 2 y 3 se repiten hasta que sólo un único mapa siga en la secuencia, o hasta que ninguno de los mapas en la secuencia se pueden combinar (es decir, hasta que la superposición de puntuación para cada posible par de mapas es igual a cero).
Si dos mapas pueden ser fusionados de varias maneras para obtener la misma puntuación, entonces, desplazar usando la combinación de la fila más pequeña. Si el resultado sigue siendo ambiguo, usar el desplazamiento de la fila más pequeña y el desplazamiento de la columna más pequeña.
Input
La entrada contiene uno o más conjuntos de datos, cada uno con entre 2 y 10 mapas. Cada conjunto de datos comienza con un entero indicando el número de mapas en la secuencia. Los mapas siguientes, cada uno empezando con una línea que contiene dos enteros NR y NC (1 - NR, NC - 10) que especifican el número de filas y columnas en el mapa inmediatamente en el siguiente NR líneas. Los primeros NC caracteres en cada una de estas NR líneas son los datos de los mapas, y rastro de caracteres en estas líneas van a ser ignorados.
La entrada para la última prueba es seguida por una línea que consiste en el número 0.
Output
Para cada conjunto de datos, muestra el número de casos de entrada (1, 2, ...) y mapas fusionados, cada uno identificado con su número de secuencia y delimitada por una frontera. La salida debe estar formateada como se muestra a continuación. No fusionar mapa que tengan más de 70 columnas.
Sample Input
5
3 5
--A-C
----D
----B
3 5
C----
D---F
B----
3 5
C----
-----
B-A-C
3 5
----D
-E--B
-----
3 5
-D--C
----G
----B
2
3 5
----A
----B
----C
3 5
A----
B----
D----
0
Sample Output
Case 1
MAP 9:
+-------------+
|-D--C--------|
|----G--------|
|----B-A-C----|
|--------D---F|
|-----E--B----|
|-------------|
+-------------+
Case 2
MAP 1:
+-----+
|----A|
|----B|
|----C|
+-----+
MAP 2:
+-----+
|A----|
|B----|
|D----|
+-----+
Prague 2003-2004
Tests-Setter: Rujia Liu
Special Thanks: Yao Guan
Traducido por: Pinedo Sarmiento, Frank Henry