Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
928 – Eternal Truths

El problema es de Grafos y se puede resolver con un BFS.
En la descripción nos dicen que hay un laberinto, y que tenemos que salir, pero con la restricción de primero movernos 1 casilla, después 2 casillas, después 3 casillas, y nuevamente 1 casilla, y así sucesivamente hasta encontrar la salida.
Como dije hay que moverse 1,2,3,1,2.. etc casillas, pero el costo de movernos esa cantidad de casillas es 1.
Ejemplo:
Tomemos de ejemplo la imagen que esta en la descripción del problema:
 El costo de la ruta es 7, ya que fueron 7 movimientos para salir del laberinto (1,2,3,1,2,3,1).

El algoritmo para movernos en el laberinto es BFS.
Cada vez que nosotros guardemos un estado en la cola, hay que estar conscientes en que tenemos que saber cuantas casillas avanzamos en el estado anterior, ademas de ir llevando la cuenta de cuantos pasos vamos dando hasta ese punto.

Para ir marcando las posiciones en donde vamos pasando, es necesaria una matriz de 3 dimensiones (int visitado[n][m][3]).
La tercera dimension en este caso sera de 3, que nos ayudara a indicar cuando pasamos por la posicion (x,y) con un paso de 1,2 o 3 pasos.

Para resaltar la importancia de la tercera dimension de tamaño 3, podemos notar que estamos en la casilla (x,y) y el ultimo paso que dimos fue de 3, por lo tanto el siguiente paso que tendremos que dar es de 1, lo cual nos llevaria a las casillas (x+1,y),(x-1,y),(x,y+1),(x,y-1).
Y ahora suponiendo que tambien estamos en la misma casilla (x,y) pero el ultimo paso que dimos fue de 1, por lo tanto el siguiente paso que tendremos que dar es de 2, los cual nos llevaria a las casillas (x+2,y),(x-2,y),(x,y+2),(x,y-2).

Como notaran, podemos llegar a casillas diferentes desde la misma posición. Por lo tanto es importante llevar en que casillas ya pasamos con pasos de 1,2 o 3 casillas.

Por ultimo, hay que revisar cuando nos movamos 1,2 o 3 casillas hacia alguna dirección las siguientes cosas:

  • Al movernos, no nos salgamos de los limites del laberinto
  • Que la casilla este desocupara
  • Que al movernos, no haya bloques intermedios bloqueando el paso

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: