Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
10422 – Knights in FEN

El problema es de Grafos y se soluciona con un BFS.
Lo que nos dan es una configuración inicial y hay que decir si es posible llegar a la configuración final que muestro a continuación, en menos de 11 movimientos.

 En este problema, lo importante es la representación del estado, que en este caso es un tablero de 5×5, así que una representación conveniente es una matriz de 5×5.
Para poder contabilizar los estados visitados, podemos utilizar un mapa de la estructura que tenemos, e ir insertando los estados conforme vallamos visitándolos.
Por ultimo hay que estar cocientes, que desde una configuración del tablero, hay 8 posibles movimientos que se pueden realizar, y cada vez que realizamos uno de estos movimientos, hay que intercambiar el centro y la pieza que corresponde de acuerdo al movimiento.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: