20 junio 2007

Solución: El tesoro

Voy a explicar la solución al problema El tesoro que puse el otro día por aquí.

Para saber la distancia mínima entre 2 puntos se utiliza el algoritmo de Dijkstra, este algoritmo obtiene la distancia mínima desde un punto de un grafo a todos los demás puntos. Cuando todos los pasos tiene el mismo coste se le suele llamar símplemente búsqueda en anchura.

Utilizando este conocido algoritmo se puede resolver fácilmente este problema. Lo única que hay que hacer es:

1 - Recorrer todo el mapa buscando los puntos (I)nicio y (F)in y guardarse en un array todos los puntos con (O)ro.
2 - Ejecutar el algoritmo de Dijkstra desde el punto I, a cada casilla del mapa se le asignará un coste CosteI(x,y) que es la distancia en casillas desde I a ese punto.
3 - Ejecutar el algoritmo de Dijkstra desde el punto F, a cada casilla del mapa se le asignará un coste CosteF(x,y) que es la distancia en casillas desde F a ese punto.
4 - Recorrer el array de oros, en cada posición de oros sumamos el valor de CosteI y CosteF para esa posición. La posición que tenga un valor CosteI+CosteF menor es el Oro que debe recoger el pirata en su camino.

Croe que esta es la solución más rápida, ya que sólo ejecuta 2 veces Dijkstra. Si alguien conoce una solución mejor que la comente...