Derrame de petróleo (2) P81175

Este problema es muy parecido al anterior problema de derrame de petróleo, excepto que en cada casilla hay corrientes marinas que hacen que el petróleo se desplace más rápidamente en una dirección que en otra. En concreto:

• En ausencia de corrientes, o si la corriente es perpendicular a la dirección de avance, la mancha tarda $10$ unidades de tiempo en avanzar una casilla.

• Si la corriente, de intensidad $I$, es paralela a la dirección de avance, la mancha tarda $10-I$ unidades de tiempo en avanzar una casilla en el sentido de la corriente, y $10+I$ unidades de tiempo en el sentido contrario.

Al igual que en problema “Derrame de petróleo”, te pedimos que simules la expansión de la mancha de petróleo. Esta vez, cada casilla se especifica con dos caracteres. Las casillas sin barreras (##) y que no sean origen de la mancha (’XX’) son de la forma $dc$, donde $d$ es un dígito de $0$ a $9$ que indica la intensidad $I$ de la corriente, y $c$ es un caracter ’N’, ’E’, ’S’ o ’W’ que indica la dirección de la corriente. Se entiende que la corriente tiene intensidad $I=0$ en las casillas que son origen de la mancha.

Entrada

El formato de entrada es prácticamente idéntico al del problema “Derrame de petróleo”. El mapa se da con una línea con los números $n$ y $m$ (filas y columnas), seguido de $n$ líneas con $m$ pares de caracteres cada una, separados por espacios, con la descripción del mapa. 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

Si aspiras a obtener 100 puntos en este problema te recomendamos usar el algorismo de Dijsktra (que no es mas que un recorrido en anchura, teniendo en cuenta que los desplazamientos entre casillas vecinas tardan tiempos distintos). ¡Si no sabes que es una cola de prioridades (priority_queue), ahora es el momento de aprenderlo! (Mira el tutorial de la STL en la web).

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 $20n\times m$. Se dará 10 puntos por cada grupo de juegos de pruebas resuelto en menos de 1 segundo de CPU por juego.