El torneo de los Tres Magos
Los aficionados a Harry Potter saben que El torneo de los Tres Magos es una competición entre alumnos de tres colegios de magia (uno de ellos el de Harry). La competición consta de tres pruebas. La última consiste en entrar en un laberinto lleno de trampas para hacerse con el tesoro que hay oculto en él: la Copa de los Tres Magos.
No vamos a desvelar aquí lo que ocurre dentro del laberinto; únicamente diremos que Harry, que es uno de los que participan en la prueba, parece buscar el tesoro moviéndose por el laberinto de forma más o menos aleatoria. No sabemos la causa de ese movimiento casi errático, pero estamos seguros de que si en lugar de él hubiera sido Hermione la que participara se habría planteado si tenía sentido seguir alguna estrategia más inteligente para alcanzar la copa.
Como cualquier amante de los laberintos sabe, una forma para salir de muchos de ellos es utilizar la "técnica de la mano derecha": se coloca la mano derecha en la pared y, sin despegarla, se va avanzando por el laberinto. Es una técnica muy cómoda porque, aunque la ruta que se sigue no es necesariamente la óptima, no requiere recordar los sitios del laberinto por los que se ha pasado.
Solo tiene una pega… no garantiza que se pueda alcanzar cualquier punto del laberinto. Solo hay certeza de que funcionará en laberintos conectados, que son aquellos en los que todas las paredes están unidas entre sí, incluídas las del exterior. Topológicamente, estos laberintos son como una única pared que se retuerce sobre sí misma para crear los pasillos del laberinto. Si el laberinto tiene "islas", entendidas como paredes que no tocan el muro exterior, o "descampados" (zonas sin paredes) la técnica de seguir la pared con la mano no necesariamente recorrerá todo el laberinto ¡y el trofeo se quedará sin encontrar!
Claro que con la estrategia de Harry de desplazarse aleatoriamente tampoco hay garantía de nada. ¿Cómo de buena es la técnica de la mano derecha si se compara con el camino más corto?
Entrada
El programa deberá leer, de la entrada estándar, múltiples casos de prueba. Cada uno comienza con una línea con dos números, 3 ≤ tx,ty ≤ 300, con el ancho y el alto del laberinto, respectivamente, en número de celdas.
A continuación aparece el mapa del laberinto con ty líneas de tx caracteres cada una. Un # indica una celda infranqueable (muro) y un punto (.) representa una zona transitable.
El mapa del laberinto tendrá siempre una muralla exterior, excepto en una celda del muro sur que es el punto de inicio de nuestro protagonista. En el interior del laberinto habrá, además, una única celda T en la posición del trofeo que hay que conseguir.
Naturalmente, por el laberinto solo es posible el movimiento por las celdas transitables. Además, los desplazamientos permitidos son en horizontal o en vertical, pero no en diagonal.
Salida
Por cada caso de prueba el programa comparará el número de pasos (cambios de casilla) requerido para llegar desde el punto inicial hasta el trofeo usando la técnica de la mano derecha y el camino más corto. En función del resultado de la comparación, el programa deberá escribir cosas diferentes:
- Si la técnica de la mano derecha llega al trofeo en el menor número de pasos posible, se escribirá IGUAL.
- Si se llega en un número de pasos subóptimo, se escribirá el número de pasos adicionales necesarios, es decir la resta entre el total y el camino más corto.
- Si es imposible llegar al trofeo con la técnica de la mano derecha, pero sí hay un camino hasta él, se escribirá INF.
- Si no hay camino para llegar desde la entrada hasta el trofeo, se escribirá IMPOSIBLE.
Entrada de ejemplo
10 3 ########## #.......T# #.######## 4 5 #### #.T# #.## #..# #.## 8 5 ######## #......# #.#T...# #......# #.###### 10 3 ########## #......#T# ###.######
Salida de ejemplo
IGUAL 2 INF IMPOSIBLE