Fișierul intrare/ieșire	diehard.in, diehard.out	Sursă	Project Euler
Autor	Project Euler	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.2 sec	Limită de memorie	8192 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Die Hard

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ă.

Date de intrare

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ă.

Date de ieșire

Î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.

Restricții

• 1 ≤ M, N ≤ 1.000
• numărul de cioburi din fiecare cameră este cuprins între 1 și 1.000
• dacă există mai multe trasee care minimizează suma numerelor de cioburi, o puteți tipări pe oricare din ele

Exemplu

Explicație

Traseul urmat de McClane este 10 – 7 – 13 – 5 – 18 – 12 – 13 – 6 – 1.