== include(page="template/taskheader" task_id="diehard") ==
Poveste și cerință...
Detectivul John McClane se războiește cu teroristul Hans Gruber într-un zgârie-nori. McClane încearcă să ajungă de pe latura vestică pe latura estică a etajului 33. Dar este în picioarele goale, iar Gruber a spart toți pereții de sticlă ai camerelor de pe etaj, umplând camerele de cioburi. McClane știe câte cioburi sunt în fiecare cameră și știe că, dacă intră într-o cameră, se va înțepa în toate cioburile din ea. McClane încearcă să-și îndeplinească misiunea în următoarele condiții:
* Harta etajului este un dreptunghi de $M$ x $N$ camere.
* McClane poate porni din orice cameră de pe latura de vest și se poate opri în orice cameră de pe latura de est.
* McClane se poate deplasa doar către est, nord sau sud. Există uși între oricare două camere adiacente pe verticală sau pe orizontală.
* McClane vrea să minimizeze suma numerelor de cioburi în care se înțeapă.
h2. Date de intrare
Fișierul de intrare $diehard.in$ ...
Fișierul de intrare $diehard.in$ conține pe prima linie numerele $M$ și [$N$]. Pe fiecare din următoarele $M$ linii se află câte $N$ numere naturale nenule, reprezentând numerele de cioburi din fiecare cameră.
h2. Date de ieșire
În fișierul de ieșire $diehard.out$ ...
În fișierul de ieșire $diehard.out$ se va scrie, pe prima linie, numărul minim de cioburi în care se va înțepa McClane. Pe a doua linie se va descrie traseul urmat de McClane: linia de pornire, urmată de un spațiu, urmată de un șir de caractere E, N sau S, lipite, care indică ordinea deplasărilor.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 1.000$
* pentru 50% din teste, $1 ≤ M, N ≤ 100$
* numărul de cioburi din fiecare cameră este cuprins între 1 și 4.000
* dacă există mai multe trasee care minimizează suma numerelor de cioburi, o puteți tipări pe oricare din ele
h2. Exemplu
table(example).
|_. diehard.in |_. diehard.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 5
99 13 5 18 35
10 7 67 12 22
10 4 83 13 10
15 12 95 6 1
| 85
2 ENEESSSE
|
h3. Explicație
...
Traseul urmat de McClane este 10 - 7 - 13 - 5 - 18 - 12 - 13 - 6 - 1.
== include(page="template/taskfooter" task_id="diehard") ==
