Herramientas de usuario
algoritmos-oia:grafos:bfs:nodos-con-niveles-de-informacion
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos:bfs:nodos-con-niveles-de-informacion [2018/01/05 22:33] santo |
algoritmos-oia:grafos:bfs:nodos-con-niveles-de-informacion [2018/01/05 22:35] (actual) santo |
||
|---|---|---|---|
| Línea 9: | Línea 9: | ||
| Concentrémonos en el último ejemplo, que es muy parecido al problema [[http://juez.oia.unsam.edu.ar/#/task/tesoro/statement|tesoro]] del Juez. | Concentrémonos en el último ejemplo, que es muy parecido al problema [[http://juez.oia.unsam.edu.ar/#/task/tesoro/statement|tesoro]] del Juez. | ||
| - | Queremos la menor cantidad de movimientos que son necesarios para llegar desde la casilla inicial hasta el tesoro, donde lo permitido es ir a un vecino si está vacío o si hay un monstruo y nos quedan flechas, aunque deberemos gastar una. | + | Queremos calcular la menor cantidad de movimientos que son necesarios para llegar desde la casilla inicial hasta el tesoro, donde lo permitido es ir a un vecino si está vacío o si hay un monstruo y nos quedan flechas, aunque deberemos gastar una. |
| Ahora, obviamente no nos sirve guardar para cada casilla la menor cantidad de movimientos hasta ella nada más, porque no sabemos si desde ahí no nos vamos a poder mover hacia casillas con monstruos, o quizás nos conviene llegar a una casilla en más pasos que el mínimo pero guardarnos una flecha para después. | Ahora, obviamente no nos sirve guardar para cada casilla la menor cantidad de movimientos hasta ella nada más, porque no sabemos si desde ahí no nos vamos a poder mover hacia casillas con monstruos, o quizás nos conviene llegar a una casilla en más pasos que el mínimo pero guardarnos una flecha para después. | ||
| Línea 25: | Línea 25: | ||
| Y para reconstruir el camino sabiendo el estado en el que terminamos, probamos ir a los vecinos, y si la menor cantidad de pasos para llegar al estado vecino es $1$ menos que para el estado actual, quiere decir que venimos de ahí. | Y para reconstruir el camino sabiendo el estado en el que terminamos, probamos ir a los vecinos, y si la menor cantidad de pasos para llegar al estado vecino es $1$ menos que para el estado actual, quiere decir que venimos de ahí. | ||
| - | Dejo un código que es prácticamente una copia del código que Agustín Gutiérrez envió en el juez, pero usando struct. Pueden ver otros códigos del juez para sacar otras ideas, pero les recomiendo elegir la manera que les sea más sencilla y "adaptable" (para mí es esta, con struct) y quedarse con ella para todos estos problemas. | + | Dejo un código basado fuertemente en una solución enviada al juez, pero usando struct. Pueden ver otros códigos del juez para sacar otras ideas, pero les recomiendo elegir la manera que les sea más sencilla y "adaptable" (para mí es esta, con struct) y quedarse con ella para todos estos problemas. |
| <code cpp tesoro.cpp> | <code cpp tesoro.cpp> | ||
algoritmos-oia/grafos/bfs/nodos-con-niveles-de-informacion.1515191592.txt.gz · Última modificación: 2018/01/05 22:33 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
