Trecere

trecere

Pentru a construi trecerea, primarul da voie constructorilor sa aleaga culoarea (din cele $n$ disponibile) pe care o va avea trecerea de pietoni precum si coloana pe care se va construi trecerea. De asemenea constructorii au voie sa schimbe intre ele dalele de pe sosea, insa efortul total va trebui sa fie cat mai mic posibil. Efortul schimbarii intre ele a doua dale de coordonatele ({$x$}, {$y$}) si respectiv ({$x{~1~}$},{$y{~1~}$}) este egal cu |{$x{~1~}$} - {$x$}| + |{$y{~1~}$} - {$y$}|, unde prin |{$a$}| s-a notat valoarea absoluta a valorii {$a$}.
!>problema/trecere?trecere.gif!

De exemplu pentru soseaua din figura alaturata, cea mai eficienta solutie este construirea unei treceri de culoare {$1$}, pe coloana {$6$}. Efortul construirii acestei sosele este {$5$}. Se vor efectua urmatoarele schimbari: dala ({$1,6$}) cu dala ({$1,7$}), dala ({$2,5$}) cu dala ({$3,6$}), dala ({$3,7$}) cu dala ({$4,6$}).
Daca exista mai multe solutii care implica acelasi efort minim, primarul prefera acea culoare avand cel mai mic cod, iar daca pentru aceasta culoare se pot construi cu acelasi efort minim, mai multe treceri, el va prefera cea mai din stanga trecere.

h2. Date de intrare

Fisierul de intrare $trecere.in$ contine pe prima linie doua numere naturale $m$ si $n$ separate printr-un spatiu, reprezentand numarul de linii respectiv de coloane ale soselei. Urmatoarele $m$ linii ale fisierului vor contine cate $n$ numere naturale cuprinse intre 1 si $n$ (inclusiv) separate prin cate un spatiu, reprezentand culorile dalelor de pe sosea.

Fisierul de intrare $trecere.in$ contine pe prima linie doua numere naturale m si n separate printr-un spatiu, reprezentand numarul de linii respectiv de coloane ale soselei. Urmatoarele m linii ale fisierului vor contine cate $n$ numere naturale cuprinse intre 1 si $n$ (inclusiv) separate prin cate un spatiu, reprezentand culorile dalelor de pe sosea.

h2. Date de iesire

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

1926