A salto de caballo P87229
Es bien sabido que el caballo del juego de ajedrez se mueve saltando en forma de L: en cada salto avanza 2 casillas en una de las cuatro posibles direcciones, y 1 casilla en una dirección perpendicular. Por ejemplo, si el caballo ocupa la posición (5,3) del tablero, después de un salto puede ocupar una de las posiciones siguientes: (3,2), (3, 4), (4,1), (4,5), (6,1), (6,5), (7,2) y (7,4).
Se te pide que digas cuál es el mínimo número de saltos que necesita un caballo para llegar a una de las posiciones objetivo.
Entrada
La entrada contiene una línea con dos números n y m, con el número de filas y columnas del tablero. A continuación, n líneas de m caracteres cada una describiendo el tablero:
- Un carácter ’.’ indica una casilla libre.
- Un carácter ’C’ indica la posición inicial del caballo. Todo tablero contiene una única casilla de este tipo.
- Un carácter ’#’ indica una casilla con un obstáculo. El caballo no puede ocupar estas casillas, pero sí puede saltarlas por encima.
- Un carácter ’X’ indica una posición objetivo. Todo tablero contiene al menos una casilla de este tipo.
Salida
Escribe el mínimo número de saltos que son necesarios para que el caballo alcance alguna de las posiciones objetivo. Si esto no es posible, escribe −1. En ambos casos, escribe un salto de línea después de escribir el número.
Puntuación
- TestA: 30 Puntos
Resolver juegos de prueba (como los de los 3 primeros ejemplos) con tableros con no más de 15 casillas libres (incluyendo las posiciones objetivo y la posición inicial). El tablero está rodeado por un borde de dos obstáculos de grosor.
- TestB: Pruebas con tableros de cualquier tipo, con n,m≤ 20. 15 Puntos
- TestC: Pruebas con tableros de cualquier tipo, con n,m≤ 250. 55 Puntos
Input
8 8 ######## ######## ##X...## ##...### ##...### ##C...## ######## ########
Output
5
Input
8 8 ######## ######## ##X..X## ######## ##...### ##C...## ######## ########
Output
2
Input
8 8 ######## ######## ##X##.## ##..#.## ##...### ##C.#X## ######## ########
Output
-1
Input
8 18 ...............X.. ...........##..... .............###XX .....###..#..##.## ####....##...#.... ....##....#..#.... .C.....#######..X. .......######.....
Output
8
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++