| Caballos en FEN |
Tenemos caballos blancos y negros en un tablero de ajedrez de tamaño 5 por 5. Hay 12 de cada color y una casilla vacía. Cualquier caballo se puede mover a la casilla vacía siempre que el movimiento sea como el movimiento normal del caballo en el ajedrez (es decir, dos casillas en una dirección y una en perpendicular).
Dada una posición inicial del tablero, la pregunta es: cuál es el mínimo número de movimientos para alcanzar la posición final, que es la siguiente:
La primera línea de la entrada contiene un entero N, que indica cuántos casos de prueba existen. La descripción de cada caso es descrita a continuación:
Cada caso consta de 5 líneas; cada línea representa una fila del tablero de ajedrez. Las posiciones ocupadas por caballos blancos son marcadas con 0 y las posiciones ocupadas por caballos negros son indicadas con 1. El espacio corresponde a la casilla libre del tablero.
No hay ninguna línea en blanco entre los casos de prueba.
Por ejemplo, el primer caso de prueba de los ejemplos de abajo corresponde a la siguiente configuración:
Unsolvable in less than 11 move(s).
En otro caso la salida será del tipo:
Solvable in n move(s).
siendo n <= 10.
La salida para cada caso debe aparecer en una única línea como se muestra en el ejemplo de salida.
2 01011 110 1 01110 01010 00100 10110 01 11 10111 01001 00000
Unsolvable in less than 11 move(s). Solvable in 7 move(s).