Reinos P42782

“¡Que cada siervo pague sus impuestos a la capital del reino que le quede más cerca!”. Y dicho esto, los como mucho 26 nobles del reino se besaron mutuamente en la boca y firmaron una paz firme y durarera. La mayoría de siervos tampoco tenían motivo para quejarse: no tendrán que moverse demasiado para pagar los impuestos.

Se te pide que hagas un programa que, a partir del mapa del reino, calcule cuantas monedas de oro cobrará cada noble, sabiendo que:

• Los siervos se mueven horizontal y verticalmente (pero no en diagonal).
• Las casillas con letras A-Z (como mucho una por cada letra) contienen las capitales del reino.
• Las casillas con punto . son casillas transitables.
• Las casillas con un símbolo # son casillas con agua: los siervos no pueden avanzar por ellas.

Entrada

Una número arbitrario de casos. Cada caso empieza con una línea con dos enteros f y c, seguido de f filas de c caracteres cada una con la descripción del mapa (caracteres A-Z,.,#, y de una línea con 3 guiones.

Salida

Para cada caso, escribe el mapa, usando letras mayúsculas para indicar a qué reino deberá pagar impuestos un siervo que viviera en una de las casillas transitables. Escribe un asterisco (*) en aquellas casillas en las que los siervos deberían pagar impuestos a más de una capital. No modifiques las casillas que corresponden a siervos que no pagan impuestos (porque no puede llegar a ninguna capital) o las casillas con agua.

Escribe una línea con tres guiones al final de la salida de cada caso de pruebas.

Puntuación

• TestA:  ‍20 Puntos ‍

  Entradas donde f,c≤ 10, donde siempre hay únicamente dos reinos A y B, y donde no hay casillas con agua, como en el Ejemplo ‍1.

• TestB:  ‍20 Puntos ‍

  Entradas donde f,c≤ 50, donde hay cualquier cantidad de reinos, y donde no hay casillas con agua, como en el Ejemplo ‍2.

• TestC:  ‍30 Puntos ‍

  Entradas donde f,c≤ 50 de cualquier tipo, como en el Ejemplo ‍3.

• TestD:  ‍30 Puntos ‍

  Entradas donde f,c≤ 500 de cualquier tipo.