Derrame de petróleo P30409

Te pedimos que simules la expansión de un derrame de petróleo en el océano, sabiendo que la mancha se origina en los puntos marcados con una ‘X’, que las casillas con un ‘.’ corresponden a zonas de mar abierto por las que la mancha puede extenderse a razón de 1 asilla por unidad de tiempo, y que las casillas con un ‘#’ indican barreras por las que la mancha no puede extenderse.

En el instante de tiempo $t=0$ la mancha (simbolizada por n ‘’) ocupa la casilla origen del derrame, y en cada unidad de tiempo posterior la mancha se expande a las cuatro casillas vecinas de cualquier casilla previamente ocupada.

Entrada

Cada juego de pruebas está formado por un mapa y diversas preguntas. El mapa se da con una línea con los números $n$ y $m$ (filas y columnas), seguido de $n$ líneas de $m$ caracteres cada una con la descripción del mismo. Al menos habrá un origen del derrame, pero puede haber más de uno.

A continuación, una secuencia de líneas, cada una de las cuales con un instante de tiempo $t_i\geq 0$. Los tiempos $t_1, t_2, \ldots$ se dan en orden creciente.

Salida

Para cada instante de tiempo $t_i$, escribe el mapa con el estado del derrame en el instante de tiempo $t_i$, siguiendo el formato indicado. Separa dos mapas con una cadena de $m$ caracteres ‘=’.

Pista

Para obtener 100 puntos, probablemente tendrás que saber qué es un recorrido en anchura. Es mucho más fácil de lo que parece, especialmente si aprendes a usar una cola (o ‘queue’).

Puntuación

Habrá 10 grupos de juegos de prueba. Los juegos de prueba del grupo $i$-ésimo tendrán mapas donde $n,m$ serán, como mucho, 3, 5, 8, 10, 20, 40, 60, 100, 250 y 500. No se pedirá escribir más de $15$ instantes de tiempo, que nunca serán superiores a $n\times m$. Se dará 10 puntos por cada grupo de juegos de pruebas resuelto.