Wind Charger
Jessy Deral se acaba de comprar una nave Wind Charger último modelo. Es de la marca Edison, famosa por sus eficientes naves eléctricas que pueden recargar sus baterías incluso en mitad del vacío aprovechando la energía de los vientos estelares de los agujeros de gusano.
Para ponerla a prueba, quiere ir desde su planeta natal, Drelec Trón, al de su lugar de vacaciones, Dargar Beos. Tiene las baterías con suficiente energía como para llegar pero, como está muy preocupada por la entropía del universo, quiere hacerlo con el menor consumo neto posible. No le importa tardar un poco más siempre que al llegar a su destino las baterías terminen lo más cargadas posible.
Tiene el mapa estelar, que se compone de una cuadrícula de W×H celdas. Ella comienza en la esquina superior izquierda y tiene que llegar a la esquina inferior derecha, desplazándose únicamente en horizontal o vertical. Cada desplazamiento le consume una unidad de energía de las baterías.
En algunas celdas hay agujeros negros que las hacen intransitables. Otras son la entrada a agujeros de gusano que terminan en celdas a veces muy alejadas. Algunos agujeros de gusano suponen un coste eléctrico grande pero otros tienen viento estelar en su interior y las baterías de la Wind Charger reciben mucha energía y se recargan. Si la nave cae en una celda con la entrada a un agujero de gusano siempre entra en él; no hay forma de salir de esa celda de otra manera.
Jessy quiere saber cuál es el consumo mínimo que puede conseguir para llegar a su destino. El problema es que su preocupación por el ahorro llega a límites de obsesión y si ve que hay una forma de recuperar más y más energía puede que entre en bucle y no llegue nunca a su destino. Si la ocurriera eso, sus baterías explotarían al no poder almacenar tanta energía.
Entrada
El programa deberá procesar múltiples casos de prueba. Cada uno comienza con dos números, 1 ≤ W, H ≤ 30 con el número de celdas a lo ancho y a lo alto del mapa estelar de Jessy. Drelec Trón y Dargar Beos son lugares distintos, por lo que W y H nunca serán simultáneamente 1.
A continuación vienen H líneas de W caracteres cada una representando el mapa. El carácter "." indica una celda vacía transitable por la Wind Charger, el carácter "#" representa una celda con un agujero negro no transitable, y el carácter "O" representa la entrada de un aguero de gusano.
Tras el mapa vendrá una línea por cada celda de tipo "O", indicando las características de cada una de ellas. Primero aparece la información de las celdas "O" de la primera fila, de izquierda a derecha, luego la información de las de la segunda fila, y así sucesivamente hasta llegar a la última fila.
La información de cada celda de tipo "O" se compone por tres números, 1 ≤ x ≤ W, 1 ≤ y ≤ H y −1000 ≤ e ≤ 1000 con la posición de salida del agujero de gusano y la cantidad de energía que consume atravesarlo. La posición (1,1) se corresponde con la celda superior izquierda, desde la que sale Jessy, y la posición (W,H) es la inferior derecha, destino de Jessy. Un valor negativo en el consumo e indica que se recupera energía y las baterías se recargan.
Se garantiza que en la esquina superior izquierda o en la esquina inferior derecha siempre habrá celdas transitables ".", y que la salida de un agujero de gusano nunca ocurrirá en una celda con un agujero negro.
Salida
Por cada caso de prueba el programa escribirá EXPLOSION si Jessy, obsesionada por su afán de ahorro, puede terminar en un bucle de recarga de la batería que haga que termine explotando.
Si eso no puede ocurrir, el programa escribirá IMPOSIBLE si Jessy no puede llegar a su destino pese a tener energía suficiente desde el principio. En otro caso, el programa escribirá el mínimo consumo neto de batería que se puede conseguir para llegar del origen al destino. Se entiende por consumo neto la resta de la cantidad de energía consumida menos la recuperada, de modo que, por ejemplo, un valor negativo indicará que se ha recuperado más energía de la consumida.
Ten en cuenta que, para Jessy, antes de su afán de ahorro está su afán de descanso. En cuanto pasa por su destino, Dargar Beos, salta de la nave y se olvida de todo.
Entrada de ejemplo
5 3 ...#. ..#.. .#... 3 3 ..O .#. ... 2 3 -2 3 3 ..O .#. ... 2 1 -2
Salida de ejemplo
IMPOSIBLE 1 EXPLOSION