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

În regiunea Ionia a lumii greceşti antice, regiune ce corespunde teritoriului actual al Mării Egee, există mai multe insule. Harta mării este reprezentată de o matrice de dimenisuni N x M, având valori de 1 şi 0, iar fiecare element din matrice reprezintă o zonă de dimensiune 1 x 1 din mare. Liniile matricei sunt numerotate de la 1 la N, de sus în jos, iar coloanele de la 1 la M, de la stânga la dreapta. Astfel, colţul din stânga sus al matricei este asociat zonei (1, 1), iar colţul din dreapta jos corespunde zonei (N, M). Un element care conţine valoarea 0 reprezintă faptul că în acea zonă se află apă. O insulă este determinată de un dreptunghi format în totalitate din valori de 1. Se garantează faptul că toate zonele care conţin valoarea 1 formează dreptunghiuri valide şi că oricare două insule sunt separate de apă.
De exemplu, Figura 1 de mai jos reprezintă o hartă validă, în timp ce Figura 2 şi Figura 3 NU reprezintă o hartă validă.

În regiunea Ionia a lumii grece?ti antice, regiune ce corespunde teritoriului actual al M?rii Egee, exist? mai multe insule. Harta m?rii este reprezentat? de o matrice de dimenisuni N x M, având valori de 1 ?i 0, iar fiecare element din matrice reprezint? o zon? de dimensiune 1 x 1 din mare. Liniile matricei sunt numerotate de la 1 la N, de sus în jos, iar coloanele de la 1 la M, de la stânga la dreapta. Astfel, col?ul din stânga sus al matricei este asociat zonei (1, 1), iar col?ul din dreapta jos corespunde zonei (N, M). Un element care con?ine valoarea 0 reprezint? faptul c? în acea zon? se afl? ap?. O insul? este determinat? de un dreptunghi format în totalitate din valori de 1. Se garanteaz? faptul c? toate zonele care con?in valoarea 1 formeaz? dreptunghiuri valide ?i c? oricare dou? insule sunt separate de ap?.
De exemplu, Figura 1 de mai jos reprezint? o hart? valid?, în timp ce Figura 2 ?i Figura 3 NU reprezint? o hart? valid?.

!problema/arhipelag2?tabel.png!

h2. Cerinţă

h2. Cerin??

Ionienii, fiind oameni practici, doresc construirea unui far-bibliotecă (aşezat pe o platformă 1 x 1), într-o zonă acoperită de apă. Poziţia platformei va fi aleasă într-o celulă C astfel încât suma distanţelor dintre toate insulele şi C să fie minimă. Distanţa dintre o celulă C şi o insulă este definită ca fiind minimul dintre distanţele Manhattan dintre C şi fiecare celulă care aparţine insulei (distanţa poate trece atât prin alte insule, cât şi prin zone acoperite de apă).
Distanţa Manhattan dintre două celule aflate pe linia x1 şi coloana y1, respectiv pe linia x2 şi coloana y2, este definită ca |x1 – x2| + |y1 – y2|, unde |x| reprezintă valoarea absolută a lui x.

Ionienii, fiind oameni practici, doresc construirea unui far-bibliotec? (a?ezat pe o platform? 1 x 1), într-o zon? acoperit? de ap?. Pozi?ia platformei va fi aleas? într-o celul? C astfel încât suma distan?elor dintre toate insulele ?i C s? fie minim?. Distan?a dintre o celul? C ?i o insul? este definit? ca fiind minimul dintre distan?ele Manhattan dintre C ?i fiecare celul? care apar?ine insulei (distan?a poate trece atât prin alte insule, cât ?i prin zone acoperite de ap?).
Distan?a Manhattan dintre dou? celule aflate pe linia x1 ?i coloana y1, respectiv pe linia x2 ?i coloana y2, este definit? ca |x1 – x2| + |y1 – y2|, unde |x| reprezint? valoarea absolut? a lui x.

h2. Date de intrare

Fişierul de intrare $arhipelag2.in$ conţine, pe prima linie, valorile N şi M, având semnificaţia din enunţ. Următoarele N linii conţin câte M valori binare, separate de câte un spaţiu, reprezentând harta mării.

Fi?ierul de intrare $arhipelag2.in$ con?ine, pe prima linie, valorile N ?i M, având semnifica?ia din enun?. Urm?toarele N linii con?in câte M valori binare, separate de câte un spa?iu, reprezentând harta m?rii.

h2. Date de ieşire

h2. Date de ie?ire

Fişierul de ieşire $arhipelag2.out$ va conţine o pereche de numere naturale, reprezentând linia si coloana celulei alese de ionieni pentru construcţie. Dacă există mai multe soluţii posibile, se va alege cea care are linia minimă. Dacă în continuare există mai multe soluţii, se va alege cea care are coloana minimă.

Fi?ierul de ie?ire $arhipelag2.out$ va con?ine o pereche de numere naturale, reprezentând linia si coloana celulei alese de ionieni pentru construc?ie. Dac? exist? mai multe solu?ii posibile, se va alege cea care are linia minim?. Dac? în continuare exist? mai multe solu?ii, se va alege cea care are coloana minim?.

h2. Restricţii

h2. Restric?ii

* $Pentru teste în valoare de 15 puncte, 1 <= N, M <= 50$

* $Pentru alte teste în valoare de 20 de puncte, 1 <= N, M <= 300, iar numărul de insule din arhipelag nu depăşeşte 300$

* $Pentru alte teste în valoare de 20 de puncte, 1 <= N, M <= 300, iar num?rul de insule din arhipelag nu dep??e?te 300$

* $Pentru alte teste în valoare de 20 de puncte, 1 <= N, M <= 300$
* $Pentru restul de teste, 1 <= N, M <= 1000$

* $Se garantează că există cel puţin o zonă acoperită de apă$

* $Se garanteaz? c? exist? cel pu?in o zon? acoperit? de ap?$

h2. Exemplu

table(example). |_. arhipelag2.in |_. arhipelag2.out |_. Explicaţie |

table(example). |_. arhipelag2.in |_. arhipelag2.out |_. Explica?ie |

| 7 7
0 1 0 1 0 1 1
0 1 0 1 0 1 1

1 1 0 1 0 1 1
1 1 0 1 0 1 1
|2 3

|Notând cu D(x1, y1, x2, y2) insula determinată de
dreptunghiul având colţul stânga sus în (x1, y1) şi colţul
dreapta jos în (x2, y2), arhipelagul conţine următoarele insule:
D1(1, 2, 2, 2), D2(1, 4, 7, 4), D3(1, 6, 2, 7), D4(6, 1, 7, 2) şi
D5(6, 6, 7, 7). Notând cu dist(D) distanţa dintre celula (2, 3) şi
insula D, distanţele sunt următoarele:

|Notând cu D(x1, y1, x2, y2) insula determinat? de
dreptunghiul având col?ul stânga sus în (x1, y1) ?i col?ul
dreapta jos în (x2, y2), arhipelagul con?ine urm?toarele insule:
D1(1, 2, 2, 2), D2(1, 4, 7, 4), D3(1, 6, 2, 7), D4(6, 1, 7, 2) ?i
D5(6, 6, 7, 7). Notând cu dist(D) distan?a dintre celula (2, 3) ?i
insula D, distan?ele sunt urm?toarele:

dist(D1) = min(|2 – 1| + |3 – 2|, |2 – 2| + |3 - 2|) = 1,

dist(D2) = 1, dist(D3) = 3, dist(D4) = 5 şi dist(D5) = 7.

dist(D2) = 1, dist(D3) = 3, dist(D4) = 5 ?i dist(D5) = 7.

|
|4 4
0 0 1 1

0 0 0 0
| 1 2
|Pentru fiecare dintre celulele (1, 2), (2, 2), (3, 2), (4, 3)

si (4, 4), distanţa dintre celulă şi singura insulă existentă în
acest exemplu este aceeaşi. Se va alege cea care are linia
minimă, iar în caz de egalitate se va alege cea care are coloana
minimă. Astfel, celula (1, 2) reprezintă soluţia.

si (4, 4), distan?a dintre celul? ?i singura insul? existent? în
acest exemplu este aceea?i. Se va alege cea care are linia
minim?, iar în caz de egalitate se va alege cea care are coloana
minim?. Astfel, celula (1, 2) reprezint? solu?ia.

|

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

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