== include(page="template/taskheader" task_id="sotron") ==
Poveste si cerinta...
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
h2. Cerinta
Sa se scrie un program care sa determine cel mai mare punctaj care se poate obtine jucand sotron dupa regulile stabilite.
h2. 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.
h2. 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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 240$
* numerele din fiecare casuta sunt intregi cuprinse in intervalul [{$-100, 100$}].
h2. Exemplu
table(example). |_. sotron.in |_. sotron.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
...
Punctajul obtinut este $3+(-2)+3+7+10=21$
!problema/sotron?sotron.gif!
== include(page="template/taskfooter" task_id="sotron") ==
== SmfTopic(topic_id="...") ==
