|
Titlul: Problema valet Scris de: Alexandru Valeanu din Ianuarie 04, 2013, 16:19:10 Am si eu nevoie de niste indicatii pentru problema valet.
Mentionez ca nu vreau niciun fel de sursa doar indicatii de cum sa fac lee-ul. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1351 Titlul: Răspuns: Problema valet Scris de: George Marcus din Ianuarie 04, 2013, 17:51:19 Trebuie sa afli distanta de la X la (1,1). Bagi in coada celula unde se afla X si apoi, cat timp ai cel putin o celula in coada incerci sa mergi in cele 4 directii. Daca ai gasit o celula invecinata la care poti sa ajungi cu un numar mai mic de mutari din celula curenta o bagi in coada(daca nu este deja - trebuie sa retii asta undeva) si ii actualizezi distanta. Rezultatul va fi distanta calculata pentru celula (1,1).
Titlul: Răspuns: Problema valet Scris de: Alexandru Valeanu din Ianuarie 04, 2013, 18:47:00 Nu cred ca merge sa fac lee doar de la pozitia actuala deoarece in an doiles exemplu nu am cum sa ies direct ( fara sa mut alte masini ). Imi trebuie o idee de cum sa mut masinile ...
Titlul: Răspuns: Problema valet Scris de: George Marcus din Ianuarie 04, 2013, 18:58:48 Mda, scuze. Am citit enuntul la repezeala si am scris prostii.
Titlul: Răspuns: Problema valet Scris de: Gavrila Vlad din Ianuarie 05, 2013, 20:10:00 Nu prea merge Lee obisnuit la problema asta; incearca un Lee in 4 dimensiuni:
d[ x ][ y ][ i ][ j ] - numarul minim de pasi a. i. sa ajungi zona libera sa se afle la (x, y), iar masina ce trebuie scoasa la (i, j) De aici ai doua cazuri (te las pe tine sa afli recurenta propriu-zisa): 1. Misti zona libera intr-o pozitie alaturata cu cost de o miscare (efectiv muti o masina-obstacol in zona libera) 2. Interschimbi masina ce trebuie scoasa cu zona libera, daca cele doua sunt alaturate. Daca mai ai nelamuriri te rog sa mai postezi aici :) Titlul: Răspuns: Problema valet Scris de: Simoiu Robert din Ianuarie 05, 2013, 20:29:17 Aceasta problema a fost data la FII Competition 2011, problema safeu, Runda a 3-a (parca). Are si solutie oficiala, si de asemenea o solutie scoasa de colegul meu, Spatarel Dan, in complexitate mult mai mica :).
[LE] Uite aici (http://www.fiicompetition.ro/f11/wp-content/uploads/2011/03/solutie_safeu.pdf) solutia. Titlul: Răspuns: Problema valet Scris de: Alexandru Valeanu din Ianuarie 06, 2013, 15:07:44 Multumesc pentru ajutor!
Daca mai am ceva nelamuriri o sa mai scriu! :) |