gard

Time limit: 0.7s Memory limit: 20MB Input: gard.in Output: gard.out

Prâslea cel Voinic a găsit grădina cu meri cu mere de aur, dar are acum probleme cu paza acestora. A stat treaz ani la rând până când a decis să construiască un gard în jurul lor, astfel încât să poată dormi liniştit.

Grădina are forma unui pătrat cu latura NN metri. Prâslea a împărţit grădina în N×NN \times N pătrate de 1m21 m^{2} , pătrate aranjate pe NN linii (numerotate de la 11 la NN) şi NN coloane (numerotate de la 11 la NN). Fiecare măr se află în unul dintre aceste pătrate.

Pentru a construi gardul, Prâslea a decis să selecteze un şir de pătrate în care primul şi ultimul pătrat, precum şi oricare 22 pătrate consecutive în şir au cel puţin un punct comun. Un pătrat poate fi ales în şir o dată sau de mai multe ori. În fiecare pătrat din şir Prâslea va plasa un stâlp uriaş. Gardul format din aceşti stâlpi împarte grădina în două zone (interior şi exterior). Toţi merii trebuie să se afle în interior. Un pătrat este considerat în interior dacă nu există drum de la un pătrat situat pe marginea grădinii (linia 11, coloana 11, linia nn sau coloana nn) la pătratul respectiv. Un drum este un şir de pătrate, astfel încât oricare două pătrate consecutive pe drum au o latură comună, pătratele de pe drum fiind libere (pătrate care nu conţin stâlpi).

Plasarea unui stâlp într-un anumit pătrat are un anumit cost. Dacă un pătrat apare de mai multe ori în şirul ales de Prâslea atunci costul va fi adunat de tot atâtea ori la costul total.

Cerinţă

Scrieţi un program care să determine costul total minim de construire a gardului respectând condiţiile din enunţ.

Date de intrare

Pe prima linie a fişierului de intrare gard.in este scris numărul natural NN reprezentând dimensiunea grădinii. Următoarele NN linii conţin câte NN numere separate prin câte un spaţiu. Dacă al jj-lea număr de pe linia ii a fişierului este -11 atunci pătratul din grădină situat pe linia i1i-1 şi coloana jj conţine un măr; altfel acel număr reprezintă costul de plasare a unui stâlp în pătratul de pe linia i1i-1 şi coloana jj.

Date de ieşire

Fişierul de ieşire gard.out va conţine o singură linie pe care va fi scris un număr natural reprezentând costul minim total de plasare a stâlpilor.

Restricții și precizări

  • 2<N<362 < N < 36
  • 0<0 < numărul de meri <6< 6
  • Costul plasării unui stâlp este un număr natural mai mare sau egal cu 00 şi mai mic decât 6 6666 \ 666.
  • Nu vor exista meri pe marginea grădinii (linia 11, coloana 11, linia NN sau coloana NN).
  • Evident, nu se poate plasa un stâlp într-un pătrat ce conţine un măr.

Exemplu

gard.in

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

gard.out

9

Explicație

Şirul de pătrate ales pentru plasarea stâlpilor este următorul:

După cum observaţi, pătratul de cost 44 dintre cei doi meri a fost ales de 22 ori.

Log in or sign up to be able to send submissions!