16 junio 2007

El tesoro

Eres un pirata y has de viajar por un mapa desde I (de inicio) hasta F (de fin). El mapa es una cuadrícula y moverse hacia el norte, sur, este y oeste cuesta 1. No se puede ir en diagonal y los símbolos # son paredes por las que no se puede pasar. En el mapa hay varios tesoros marcados con O (de oro).

Ejemplo de mapa:

###############
# #
F # # O #
# #O ###### #
# #### O I
# # ######
# #
###############


¿Cuál es el camino mínimo para ir de I a F recogiendo al menos un tesoro?
No hace falta programarlo, simplemente decir cómo se podría obtener el mejor camino.

Ánimo.