Esporas Depredadoras P15676

Se tienen diversos tipos de plantas, las unas más depredadoras que las otras. Para cada tipo de planta se conoce el radio de circunferencia a la que llegan sus esporas (por ejemplo, las esporas de una planta con radio de circunferencia 2 siempre caen a distancia 2 de la planta original). Además, las esporas únicamente germinan sobre coordenadas enteras. En el caso que hubiera otra planta ocupando la posición, la espora la matará y ocupará su lugar si pertenece a un tipo más depredador del que ya había.

Suponiendo que partimos del año 0, se te pide que devuelvas la situación en la que se encontrarán las plantas después de $X$ años. Puedes asumir que, al igual que los elfos, estas plantas ni enferman ni mueren de vejez.

Entrada

Cada entrada está formada por varios casos de prueba. La primera línea de cada caso de pruebas contiene los tipos de plantas (una secuencia de letras mayúsculas A–Z del alfabeto), según su capacidad depredadora (la primera de la secuencia es la más depredadora de todas). La siguiente línea tiene tantos números positivos como tipos de plantas, y describe sus radios. A continuación, una línea con los tamaños (filas y columnas) del jardín donde viven las plantas, y la descripción de la situación actual (año 0) del jardín: letras mayúsculas indican las plantas existentes, y el carácter * indica un espacio vacío. Por último, una línea con el entero $X$.

Salida

Para cada caso de pruebas, escribe el estado en el que queda el jardín transcurridos $X$ años, siguiendo el mismo formato que la entrada. Escribe un salto de línea después de cada caso de pruebas.

Puntuación

• Easy:

  Resolver mapas pequeños con jardines de no más de 100 puntos enterors y como mucho 3 plantas.

• Hard:   Resolver todo tipo de entradas.