1052 Rege

[•wefgef]

Aici puteţi discuta despre problema Rege.

[•ctlin04]

Poate se-mi dea cineva niste sugestii referitor la structura testelor 4,7 si 8, fac PD dar iau TLE la testul 4 si 7, iar la 8 WA, probabil ca imi cicleaza programul deoarece cu un brute force testul 4 a intrat lejer in timp, ma ajuta cineva sa iau si eu suta la problema asta, pls  

[•PlayLikeNeverB4]

In loc sa te intereseze structura testelor, ar trebui sa te intereseze corectitudinea algoritmului.

[•ctlin04]

Ei bine atunci poate careva sugestii despre structura algoritmului si cazuri speciale 

[•PlayLikeNeverB4]

Nu cred ca exista vreun caz special. E o parcurgere in latime a tablei de sah. Pornesti din (l1,c1) si pargurgi toata tabla. Poate ai incurcat N cu M undeva? Verifici daca vecinul nu iese de pe tabla? Aa si sa nu introduci de 2 ori acelasi element in coada.

[•ctlin04]

Ms pentru atentie George Marcus, asa ma gindeam si eu ca nu pot fi careva cazuri speciale, doar poate cazul cind coincide pozitia initiala cu cea finala dar si acesta nu prezinta o problema, defapt greseala era mai banala decit credeam, am scapat un ' - ' in loc de '+' dupa ce am observat si am reparat am luat 100  
Apropo de ce sa parcurgi toata tabla, e deajuns sa parcurgi doar pna in l2,c2.

[•PlayLikeNeverB4]

Aa, da, ai dreptate. Din cauza vreunui motiv ciudat credeam ca daca nu parcurgi toata tabla nu prinzi toate posibilitatile.
P.S.: Vezi ca nu te-ar fi ajutat structura testelor?

[•Codrin09]

Stiti cumva daca la testul 18 este vre-un caz particular?Doar la el nu imi iese si nu stiu de ce...

[•Georginsky]

Am facut parcurgerea in latime (lee) pana la [l2, c2]... Apoi am facut o functie recursiva care merge din pozitia [l2, c2] inapoi la [l1, c1] pentru a afla numarul de drumuri minime posibile. Din pacate, nu prea intra in timp. Aveti careva vreun hint pentru a afla numarul de drumuri? 

[•PlayLikeNeverB4]

Poti sa afli numarul de drumuri pe masura ce faci parcurgerea in latime. Numarul de drumuri pana in (l1,c1) este 1. Gandeste-te cum poti sa "transmiti" mai departe numarul de drumuri in timpul parcurgerii.

[•FlorinHaja]

E corect dacă stabilesc un număr A = numărul posibil de pași pe diagonală, plus un număr B = numărul posibil de pași pe orizontală/verticală și afișez Catalan(A+B)?

[•marcudanf]

Pentru cei care au solutia de 10 puncte si nu inteleg care sunt celalte cazuri (ca mine): de exemplu, pentru a merge 2 patratele in sus poti sa o iei 2 pasi in sus, nu?? Dar drum minim este considerat si urmatorul: un pas pe diagonala sus stanga si unul pe diagonala sus dreapta.
Sper ca am ajutat si ca m-am exprimat destul de clar