Problema B - Problem B The Toxic Clouds of Proxima III
Autor: Rui Mendes (Universidade do Minho)
Tipo de problema: Grafos (Pesquisa em Profundidade / Cortes)
Número de ficheiros de teste: 7
Este é um problema clássico de concursos. Estamos no meio de um qualquer "labirinto" e temos de encontrar uma "saída". Neste caso tinhamos uma energia que decrescia em cada casa que passavamos.
O problema podia ser resolvido de várias maneiras, mas dadas as dimensões máxima (500x500) uma simples pesquisa em profundidade (recursiva) bastava. Tínhamos apenas de ter o cuidado de ao "percorrer" o mapa ir guardando a melhor energia e número de passos com que chegamos a cada casa. Se ao chegarmos a um sítio, já lá tivessemos passado com menor energia (ou igual energia mas menor ou igual número de passos), então não vale a pena continuar, pois nunca iremos melhorar o caminho (um corte na pesquisa, portanto - branch and bound)
No final bastava imprimir qual o melhor caminho, caso existisse.
Uma nota final para dizer que havia maneira de percorrer o mapa de tal modo que quando chegassemos a primeira vezà saída, teriamos a certeza de ter chegado da melho maneira possível. Bastava usar um Dijkstra modificado. E de cada vez, iriamos explorar o nó ligado a um nó já percorrido de tal modo que minimizasse o binómio (energia,nºpassos) da maneira pedida.
Ligações interessantes: