El Salto del caballo
Se dispone de una superficie rectangular "cuadriculada", es decir, formada por un entramado de
posiciones o casillas (como ocurre, por ejemplo, con un tablero de ajedrez). Nos interesa buscar
caminos dentro de esta superficie que cumplan ciertas condiciones, teniendo en cuenta que
algunas de las casillas no pueden formar parte de dichos caminos (para entendernos,
representan obstáculos en la superficie).
Problema
Dada una superficie rectangular de dimensión n×m, realizar un programa que la recorra
partiendo de una casilla inicial y llegando a una casilla final según las reglas siguientes:
· Todas las casillas deberán ser visitadas excepto las casillas marcadas como no
visitables.
· No se podrá visitar más de una vez cada casilla.
· El salto de una casilla a otra deberá realizarse siguiendo las reglas de
movimiento del caballo de ajedrez. Esto es, desde una casilla sólo se
podrá avanzar a aquellas resultantes de avanzar una posición en línea
recta y otra en diagonal en la misma dirección. El esquema muestra en
rojo las casillas accesibles al caballo:
El programa deberá calcular la secuencia de casillas visitadas desde la inicial hasta la final. En
caso que no exista ninguna solución, el programa debe detectar esta situación e informar.
Imagen tomada de Wikipedia
Entrada
La entrada del programa consiste en una secuencia de líneas, que tendrá el siguiente formato:
· La primera línea contiene la dimensión de la superficie, es decir, el número n de
columnas y el número m de filas. Los dos valores son por lo menos 1 y a lo mas 16.
· La segunda línea contiene la posición inicial y la posición final, cada posición siendo
dos enteros, la columna y la fila respectivamente. Puedes suponer que las dos
posiciones están dentro de los límites de la superficie.
· A continuación, m líneas más. Cada línea representa una fila de la superficie, y
contiene n caracteres, uno por columna. Cada uno de estos caracteres puede ser 'V'
o 'N', dependiendo de si la posición correspondiente es visitable o no. Los
caracteres aparecen separados por un único carácter "espacio".
A efectos de numeración, debe considerarse que las filas van de 1 a m y las columnas de 1 a n.
Salida
La salida del programa contendrá una línea por cada posición que forme parte del camino
encontrado como solución que cumpla las condiciones dadas en el enunciado. Cada posición
es un par de enteros: la columna y la fila. La primera posición de la solución será la posición
inicial, y la última la posición final.
Si no hay ninguna solución, la salida contendrá una única línea con el texto
“INSATISFACTIBLE”. Si existe más de una solución, cualquiera de ellas se considera válida.
La siguiente liga es de donde tome la información para realizar mi proyecto: http://docs.google.com/viewer?a=v&q=cache:AaUyJypIaKMJ:pier.guillen.com.mx/icpc-omi/icpc-2002/problema-03.pdf+el+problema+del+salto+de+caballo&hl=es&gl=mx&sig=AHIEtbRaHcd9d7eG_4NpbvBFa3qefCl5Kw
La siguiente liga muestra la emulación del programa:http://www.ciberchess.com/comun/curiosidades/cabalo/cabalo.html
Alcanzaste publicar justo antes de que yo lo califiqué (5 minutos antes) ;) Comienzas bien, pero me hubiera gustado ver más análisis explícito sobre la dificultad del problema y el comportamiento asintótico de algoritmos para ello.
ResponderEliminar