Problema valet

[•AlexandruValeanu]

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

[•PlayLikeNeverB4]

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).

[•AlexandruValeanu]

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 ...

[•PlayLikeNeverB4]

Mda, scuze. Am citit enuntul la repezeala si am scris prostii.

[•GavrilaVlad]

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

[•SpiderMan]

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 solutia.

[•AlexandruValeanu]

Multumesc pentru ajutor!
Daca mai am ceva nelamuriri o sa mai scriu!