346 Padure

[•ctlin04]

Nu cred ca pentru algoritmul implimentat de mine exista cazuri cind poate fi imbunatatit de doua ori costul unui nod, teoretic la mine fiecare celula poate fi introdusa in coada cel mult odata, eu tin un tablou auxiliar b, unde b[ i ] [ j ]=costul minim pentru a ajunge din pozitia finala in pozitia i,j plus 1; respectiv raspunsul este b[ x1 ][ y1 ] - 1; mai intii introduc in coada toate celulele care au acelasi cost ca si pozitia finala si marcez in b, apoi pentru fiecare celula din coada controlez daca are vecin de culoare diferita care inca nu a fost expadat si daca are introduc vecinul respectiv in coada apoi toate celulele de aceeasi culoare cu vecinul si respectiv marchez in b si astfel pina cind pozitia de start are valoarea 0, repectiv pentru testul:
111
122
133
144
155
111
daca vreau sa ajung din 1,1 in 6,3 atunci voi introduce in coada toate pozitiile cu costul 1, si deodata afisez solutia adica destul de repede, iar daca vreau alta pozitie e deajuns inca un pas ca se aflu solutia adica de ex cind expadez 1,2 voi nota ambele pozitii cu costul 2 si le voi pune in coada, apoi pentru 1,3 nu fac nimic, apoi voi marca pe pozitiile cu costul 3, apoi cu 4 si in final cu 5, avind toate pozitiile incluse in coada o singura data si cred ca chiar daca scot parsarea oricum acest algoritm nu v-a merge mai incet decit cel cu 2 cozi  

[•dutzul]

eu m-am gandit la solutia lui devilkind, fac un fill si dupa aia fac un graf. Ca sa nu pun muchiile de mai multe ori la un nod m-am gandit sa folosesc un set (sau map) numai ca cum zicea el pot fi pana la n^2 noduri in graf si imi pun urmatoarea intrebare:
daca declar un set <char> A[1000.000] ocupa ceva? adica per total nu bag mai mult de n^2 muchii numai ma gandesc sa nu ocupe pointerii memorie. Declararea unui set nu ocupa memorie daca e doar declarat(nu pun nimic in el)?

[•freak93]

Ba da. Fiecare set ocupa cativa bytes(Daca imi amintesc bine ocupa 12). Si fiecare element din set aduce cu el inca 8 bytes.

[•dutzul]

si <vector>,<list> ocupa ceva?

[•freak93]

vector 12 bytes si list 8 bytes. List mai ocupa 8 bytes pe element iar vector ocupa(deobicei) mai mult decat e marimea lui. Daca ai x elemente in vector el ocupa cat 2^k elemente unde k e cel mai mic numar natural astfel incat 2^k >= x

[•dutzul]

ok mersi

[•geniucos]

Ati putea sa imi dati si mie niste teste ca iau 20 cu tle dar sunt sigur ca imi cicleaza.Pe testele pe care mi le-am dat mi-a mers.
Multumesc anticipat

[•SebiSebi]

Uite aici :

Cod:

30 15 7 10 25 8
4 4 1 1 3 2 1 1 2 2 0 3 3 3 4
8 4 4 1 1 3 2 4 4 4 1 1 3 2 2
1 1 1 4 0 0 1 1 1 2 2 0 3 3 3
1 1 2 2 0 3 3 3 3 3 2 2 2 0 3
7 7 7 2 8 8 9 9 9 0 0 0 0 0 1
9 9 9 6 6 7 7 8 8 8 9 9 9 3 4
9 9 9 9 6 6 7 7 8 8 8 9 9 9 1
8 9 9 9 9 9 9 4 4 4 4 4 3 4 4
8 9 6 6 6 6 6 6 6 6 4 4 4 4 0
6 6 6 7 7 7 7 7 7 8 8 8 8 4 4
0 6 6 7 7 7 7 7 7 8 8 8 8 4 4
0 0 6 6 6 6 6 7 6 6 6 6 8 6 4
1 1 1 6 0 0 6 7 6 9 9 9 9 9 4
1 1 2 2 0 0 6 6 6 6 6 6 6 6 6
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
0 0 9 9 9 6 6 7 7 8 8 8 9 9 9
9 9 9 9 6 6 7 7 8 8 8 9 9 9 1
0 4 9 9 0 0 7 7 7 7 7 8 8 8 9
0 0 9 9 9 6 6 7 7 8 8 8 9 9 9
0 4 9 9 0 0 7 7 7 7 7 8 8 8 9
0 0 9 9 9 6 6 7 7 8 8 8 9 9 9
0 0 9 9 9 6 6 7 7 8 8 8 9 9 9
9 9 9 9 6 6 7 7 8 8 8 9 9 9 1
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8

Rezultatul e : 3

Cod:

10 17 5 10 8 17
0 4 0 5 5 4 4 8 4 4 1 1 3 2 1 1 2
8 4 4 1 1 3 2 4 4 4 1 1 3 2 2 2 0
1 1 1 4 0 0 1 1 1 2 2 0 3 3 3 2 2
1 1 2 2 0 3 3 3 3 3 2 2 2 0 3 9 2
0 4 9 9 0 0 7 7 7 7 7 8 8 8 9 9 9
0 0 9 9 9 6 6 7 7 8 8 8 9 9 9 3 4
9 9 9 9 6 6 7 7 8 8 8 9 9 9 1 1 4
1 1 1 4 0 0 6 8 8 9 9 9 9 9 9 4 4
1 1 2 2 0 0 6 6 6 6 6 6 6 6 6 6 6
0 4 2 2 0 6 6 7 7 7 7 7 7 8 8 8 8

Rezultatul e : 2
Sper sa te ajute.

[•geniucos]

Mutumesc mult!Chiar m-a ajutat

[•mvcl3]

Imi explica si mie cineva dc iau tle pe testul 9 ca nu-mi dau seama!
multumesc!

[•SebiSebi]

Trebuie sa parsezi citirea pentru 100. Si eu aveam complexitatea optima O(n*m) si luam TLE. Bafta! 

[•mvcl3]

ms fain!! am luat 100    ...aia era problema!!

[•AlexandruValeanu]

Poate sa-mi spune si mie cineva cum mai poate fi modificata sursa mea pentru a intra in timp?

[•SebiSebi]

Problema se rezolva folosind 2 cozi (nu cu o parcurgere in latime simpla). Calculezi mai intai nodurile cu distanta 0 , apoi cele cu distanta 1 , s.a. Merge mai repede asa deoarece rezultatul va fi un numar mic. Succes!

[•AlexandruValeanu]

Poate cineva sa posteze niste teste mai mari/dificile...iau la 5 teste WA si chiar nu imi explic de ce.

[•mihai.constantin]

Poate cineva sa puna testul 2, va rog? Iau 90 de puncte si nu inteleg unde am gresit...
Multumesc.

[•mihai.constantin]

Am reusit. 100p