Fişierul intrare/ieşire:gard4.in, gard4.outSursălot 2006
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test1.1 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gard 4

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Praslea cel Voinic a gasit gradina cu meri cu mere de aur, dar are acum probleme cu paza acestora. A stat treaz ani la rand pana cand a decis sa construiasca un gard in jurul lor, astfel incat sa poata dormi linistit. Gradina are forma unui patrat cu latura N metri. Praslea a impartit gradina in N*N patrate de 1m2, patrate aranjate pe N linii (numerotate de la 1 la N) si N coloane (numerotate de la 1 la N). Fiecare mar se afla in unul dintre aceste patrate. Pentru a construi gardul, Praslea a decis sa selecteze un sir de patrate in care primul si ultimul patrat, precum si oricare 2 patrate consecutive in sir au cel putin un punct comun. Un patrat poate fi ales in sir o data sau de mai multe ori. In fiecare patrat din sir Praslea va plasa un stalp urias. Gardul format din acesti stalpi imparte gradina in doua zone (interior si exterior). Toti merii trebuie sa se afle in interior. Un patrat este considerat in interior daca nu exista drum de la un patrat situat pe marginea gradinii (linia 1, coloana 1, linia N sau coloana N) la patratul respectiv. Un drum este un sir de patrate, astfel incat oricare doua patrate consecutive pe drum au o latura comuna, patratele de pe drum fiind libere (patrate care nu contin stalpi). Plasarea unui stalp intr-un anumit patrat are un anumit cost. Daca un patrat apare de mai multe ori in sirul ales de Praslea atunci costul va fi adunat de tot atatea ori la costul total.

Cerinta

Scrieti un program care sa determine costul total minim de construire a gardului respectand conditiile din enunt.

Date de intrare

Pe prima linie a fisierului de intrare gard4.in este scris numarul natural N reprezentand dimensiunea gradinii. Urmatoarele N linii contin cate N numere separate prin cate un spatiu. Daca al j-lea numar de pe linia i a fisierului este -1 atunci patratul din gradina situat pe linia i-1 si coloana j contine un mar; altfel acel numar reprezinta costul de plasare a unui stalp in patratul de pe linia i-1 si coloana j.

Date de iesire

Fisierul de iesire gard4.out va contine o singura linie pe care va fi scris un numar natural reprezentand costul minim total de plasare a stalpilor.

Restrictii

  • 3 ≤ N ≤ 35
  • 1 ≤ numarul de meri ≤ 5
  • costul plasarii unui stalp este un numar natural mai mare sau egal cu 0 si mai mic decat 6666
  • nu vor exista meri pe marginea gradinii (linia 1, coloana 1, linia N sau coloana N)
  • evident, nu se poate plasa un stalp intr-un patrat ce contine un mar

Exemplu

gard4.ingard4.out
5
3 0 10 10 10
10 1 10 0 10
0 -1 4 -1 0
10 0 10 0 0
10 10 10 10 0
9

Explicatie

Sirul de patrate ales pentru plasarea stalpilor este urmatorul:
 3  0 10 10 10
10  1 10  0 10
 0 -1  4 -1  0
10  0 10  0  0
10 10 10 10  0

Dupa cum observati, patratul de cost 4 dintre cei doi meri a fost ales de 2 ori.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content