gard4

Gard 4

== include(page="template/taskheader" task_id="gard4") ==

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 $1 m^2^$, 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.

== include(page="template/badtests") ==
 
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 $1m^2^$, 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.

h2. Cerinta

h2. 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$.

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

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

h2. Exemplu
table(example). |_. gard4.in |_. gard4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

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

== include(page="template/taskfooter" task_id="gard4") ==

1762