Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
439 – Knight Moves

Este problema es de grafos y se puede solucionar con un BFS.
Lo que nos piden es el mínimo numero de movimientos que tiene que hacer un caballo sobre un tablero de ajedrez para llegar de una posición a otra.
Basicamente lo unico que hay que hacer es colocarse en la posicion inicial donde nos encontramos y visitar los 8 vecinos posibles de una casilla, verificando que la casilla sea valida en el tablero.
Para representar una posición nosotros podemos utilizar lo que es el “pair” de la librería #include<utility>

pair<int,int> ori,dest;

Para movernos en el tablero podemos utilizar 2 arreglos que contengan las 8 posibles combinaciones de movimientos del caballo:

int x[] = {1, 1,2, 2,-1,-1,-2,-2};
int y[] = {2,-2,1,-1, 2,-2, 1,-1};

Al utilizar la cola, hay que llevar el numero de pasos que se van dando para ir contabilizando, entonces opte por utilizar una pareja relacionada con un entero:

queue<pair<pair<int,int>,int> cola;

El primer elemento de la pareja, representa la posición x,y del caballo.
La segunda parte de la pareja es un entero, que representa el numero de pasos realizados.

 

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: