\(\href{https://algomania.es/account/5}{\color{blue}{\underline{\text{buhsan}}}}\) está atrapado en un laberinto representado como una cuadrícula de n filas y m columnas. Cada celda del laberinto puede ser:
- '#' : una pared
- ' ': un espacio vacío donde puede moverse
- 'I': la posición inicial de Buhsan
- 'F': la posición final a la que debe llegar
'X': un potenciador que permite atravesar paredes
Buhsan puede moverse en las 4 direcciones cardinales (arriba, abajo, izquierda, derecha). El movimiento normal le permite moverse a una celda vacía (' ') o a un potenciador ('X').
Cuando Buhsan entra en una celda con 'X', obtiene un potenciador adicional que puede usar para entrar en una celda de pared '#'. Cada potenciador permite entrar en una celda de pared una sola vez. Se permite que Buhsan esté parado en una celda de pared, pero moverse a otra celda de pared requiere gastar otro potenciador. Una vez que se recoge un potenciador ya no se puede volver a recoger.
Buhsan quiere llegar de 'I' a 'F' gastando la menor cantidad de pasos posible. Cada movimiento cuenta como un paso, incluso si entra en una pared.
Entrada
La entrada consiste en \(n\) líneas de \(m\) caracteres cada una, representando el laberinto.
Cada carácter es uno de '#', ' ', 'I', 'F' o 'X'.
Hay exactamente un 'I' y un 'F' en la cuadrícula.
Cada fila tiene exactamente \(m\) caracteres.
Se garantiza que \(1 \le n, m \le 50\) y que no habrá más de 8 potenciadores.
Salida
Imprime un solo número: el mínimo número de pasos que Buhsan necesita para llegar de I a F.
Si es imposible llegar a F, imprime -1.