Buhsan y el laberinto

<a href="/account/5" class="font-bold"><span class="text-[#87B37A]">buh</span><span class="text-[#9CE37D]">san</span></a> 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.

##########
#X      I#
##########
## #######
##       #
########X#
##F#######
##########

27

#############
#I          #
##### #######
##### #######
#F###X#   XX#
#############

-1

#############
#I          #
##### #######
##### #######
#F###X#  XXX#
#############

29