Esconde esa cara
Al principio de los tiempos, antes de que la gravedad consiguiera hacer que nuestro planeta fuera una esfera casi perfecta, antes de que la erosión creara los cantos rodados, antes de que la naturaleza se diera cuenta de que la forma esférica era la más adecuada para muchas cosas, el mundo estaba hecho de cubos.
En aquellos días nuestro planeta (cúbico) estaba habitado por extraños seres (cúbicos) que se movían por la tierra a duras penas rotando sobre sus aristas. Pero para esos cabezas cuadradas la vida era más fácil; siendo cubos perfectos como eran y con esas limitaciones en el desplazamiento se encontraban siempre en posiciones discretas múltiplo de las longitudes de sus lados. Y, en ausencia de obstáculos, la distancia más corta entre dos puntos en campo abierto era siempre la distancia Manhattan, evitando así usar longitudes, latitudes y trigonometría esférica.
Bueno, la vida era más fácil para todos excepto para Qbo. Un defecto congénito le hizo nacer con una cara de un color distinto a las otras cinco algo que, en lugar de mostrar con orgullo, intentaba disimular dejando siempre esa cara apoyada en el suelo. Eso dificultaba los desplazamientos, claro, porque para conseguirlo algunas veces tenía que recorrer distancias más grandes y otras ni siquiera era posible.
Aunque aquellos tiempos cúbicos quedaron atrás y nada queda de nuestro simpático Qbo, es interesante analizar cómo de difícil era su vida por esa restricción autoimpuesta de disimular su cara distinta. Dado un escenario, un punto de origen y un punto de destino queremos saber cuántos pasos (o rotaciones) como mínimo tendría que haber hecho si no le hubiera importado dónde quedara su cara especial y cuántos tenía que hacer de verdad.
Entrada
La entrada está compuesta por distintos casos de prueba, cada uno representando un escenario rectangular.
Cada caso comienza con una línea con el número de baldosas en horizontal y en vertical de ese escenario (1 ≤ tx, ty ≤ 50). A continuación aparecen 2×ty + 1 líneas de 2×tx + 1 caracteres cada una con un dibujo esquemático del mapa. Los bordes están representados por líneas horizontales y verticales y las baldosas con espacios colocados en las coordenadas pares (si empezamos a contar desde el 1). Entre cada baldosa, tanto en horizontal como en vertical, hay un carácter que indica si los cubos pueden rotar para moverse entre ellas (si aparece un espacio) o si ese desplazamiento no es posible (caracteres - o | dependiendo de si la rotación es en horizontal o en vertical). Los caracteres del mapa situados en posiciones impares en ambas componentes representan las esquinas de las baldosas físicas y aparecen con un símbolo +.
La baldosa origen de Qbo se indica con la letra O mientras que el destino es una D.
Tras el último caso de prueba hay una línea con dos ceros, 0 0.
Salida
Por cada caso de prueba se escribirá una línea con dos números: la cantidad de rotaciones que deben hacer los cubos como mínimo para llegar desde el origen al destino y la cantidad que tenía que hacer Qbo para que al llegar quedara tocando el suelo la misma cara que tocaba el suelo en el origen. En ambos casos si el desplazamiento no es posible se indicará IMPOSIBLE.
Entrada de ejemplo
2 1 +-+-+ |O D| +-+-+ 2 1 +-+-+ |O|D| +-+-+ 5 1 +-+-+-+-+-+ |O D| +-+-+-+-+-+ 5 3 +-+-+-+-+-+ | D | +-+ + + + + |O | | +-+-+ + + + | | +-+-+-+-+-+ 0 0
Salida de ejemplo
1 IMPOSIBLE IMPOSIBLE IMPOSIBLE 4 4 2 8