17/12/2011, 11:48
|
| | | Fecha de Ingreso: diciembre-2011
Mensajes: 3
Antigüedad: 12 años, 4 meses Puntos: 0 | |
| Respuesta: Problema de ACM sobre 3300 - Snake pit, hallar el camino mas corto
Lo del "tablón" que se rompe una vez que pasás no debería ser problema, ya que si pasás dos veces por el mismo lado estás aumentando la cantidad de pasos sin hacer nada.
Según lo que entendí, hay dos casos principales:
1er caso: Indiana Jones puede llegar a la salida sin necesidad de agregar ningún tablón:
Como te pide "mínimo camino", tendrías que ver dónde te convendría poner un tablón para minimizar la distancia.
2do caso: La salida y la entrada no están conectadas.
En ese caso, tenés que ver dónde poner el tablón para que se conecte la salida con la entrada y ese camino tenga la mínima distancia.
Te conviene empezar haciendo la búsqueda del camino más corto para salir del laberinto, con BFS (te da igual cruzar cualquier tablón).
Si necesitás más ayuda, avisá. |