Fişierul intrare/ieşire:diehard.in, diehard.outSursăProject Euler
AutorProject EulerAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.7 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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
  • 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

Exemplu

diehard.indiehard.out
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

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici