Fişierul intrare/ieşire:sotron.in, sotron.outSursăONI 2007, clasa 9
AutorCristina BarbieruAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sotron

Pe asfalt este desenat cu creta un sotron, caroiaj format din n*n casute avand aceleasi dimensiuni (cate n casute pe fiecare din cele n randuri). In fiecare casuta este scris cate un numar intreg. Fiecare jucator are cate o piatra pe care o arunca intr-o casuta a sotronului, si sarind intr-un picior, impinge piatra din casuta in casuta, pe un anumit traseu astfel incat punctajul obtinut din suma numerelor de pe traseul parcurs sa fie cat mai mare.
Numerele din casutele sotronului sunt scrise cu doua culori albastru si alb, astfel incat sa nu existe doua casute alaturate (pe cele patru directii Nord, Est, Sud, Vest) avand numere scrise cu aceeasi culoare. Intotdeauna, prima casuta din primul rand al sotronului are inscris un numar de culoare albastra.

Se stabilesc apoi, urmatoarele reguli ale jocului:

  • la inceputul jocului, piatra poate fi aruncata in oricare casuta a sotronului. Din pozitia respectiva jucatorul isi conduce piatra pana la sfarsitul traseului stabilit de el;
  • dintr-o casuta in care numarul este scris cu albastru, piatra poate fi deplasata doar in casuta vecina pe directia Nord;
  • dintr-o casuta in care numarul este scris cu alb, piatra poate fi deplasata doar in casuta vecina pe directia Est;
  • jucatorul poate alege orice casuta (inclusiv cea in care a aruncat piatra) pentru a incheia jocul, atata timp cat piatra nu iese din sotron

Cerinta

Sa se scrie un program care sa determine cel mai mare punctaj care se poate obtine jucand sotron dupa regulile stabilite.

Date de intrare

Fisierul de intrare sotron.in are pe prima linie dimensiunea n a sotronului, iar pe urmatoarele n linii cate n numere separate de cate un spatiu, reprezentand numerele scrise in sotron.

Date de iesire

Fisierul de iesire sotron.out va contine pe prima linie un singur numar reprezentand punctajul maxim care se poate obtine jucand sotron.

Restrictii

  • 1 ≤ n ≤ 240
  • numerele din fiecare casuta sunt intregi cuprinse in intervalul [-100, 100].

Exemplu

sotron.insotron.out
5
0 -6 -5 -17 2
1 -4 7 10 5
-3 -2 3 -8 -8
-20 3 5 3 -5
-10 -15 2 2 -4
21

Explicatie

Punctajul obtinut este 3+(-2)+3+7+10=21
 

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content