Fişierul intrare/ieşire:arhipelag2.in, arhipelag2.outSursăONI 2017, clasa a 9-a
AutorMihai EnacheAdăugată deBLz0rDospra Cristian BLz0r
Timp execuţie pe test0.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 × 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ă.

Cerinţă

Ionienii, fiind oameni practici, doresc construirea unui far-bibliotecă (aşezat pe o platformă 1 × 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.

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.

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

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
  • Pentru restul de teste, 1 <= N, M <= 1000
  • Se garantează că există cel puţin o zonă acoperită de apă

Exemplu

arhipelag2.inarhipelag2.outExplicaţie
7 7
0 1 0 1 0 1 1
0 1 0 1 0 1 1
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
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, D2, D3, D4 şi
D5. 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.
4 4
0 0 1 1
0 0 1 1
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?