Î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 dimensiuni N•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ă.
Cerința
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 arhipelag.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 arhipelag.out va conține o pereche de numere naturale, reprezentând linia și 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 și precizări
- 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ște300 - 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ă
Exemplul 1
arhipelag.in
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
arhipelag.out
2 3
Explicație
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.
Exemplul 2
arhipelag.in
4 4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0
arhipelag.out
1 2
Explicație
Pentru fiecare dintre celulele (1, 2), (2, 2), (3, 2), (4, 3) și (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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Arhipelag:
// Mihai Enache
#include <iostream>
#include <fstream>
using namespace std;
const int MAX_N = 1002;
int N, M, xs, ys;
int A[MAX_N][MAX_N], cx[MAX_N], cy[MAX_N], startX[MAX_N], endX[MAX_N], startY[MAX_N], endY[MAX_N];
void computeCostForCoordinate(int n, int c[], int startHere[], int endHere[]) {
int toRight = 0;
int toLeft = 0;
for(int i = 2; i <= n; ++i) {
c[1] += (i - 1) * startHere[i];
toRight += startHere[i];
}
for(int i = 2; i <= n; ++i) {
toLeft += endHere[i - 1];
c[i] = c[i - 1] - toRight + toLeft;
toRight -= startHere[i];
}
}
int main() {
ifstream cin("arhipelag.in");
ofstream cout("arhipelag.out");
cin >> N >> M;
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
cin >> A[i][j];
}
}
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
if(A[i][j] == 1) {
int xl = i;
int xr = i;
while(A[xr + 1][j]) {
++xr;
}
int yl = j;
int yr = j;
while(A[i][yr + 1]) {
++yr;
}
for(int k = xl; k <= xr; ++k) {
for(int h = yl; h <= yr; ++h) {
A[k][h] = -1;
}
}
++startX[xl];
++endX[xr];
++startY[yl];
++endY[yr];
}
}
}
computeCostForCoordinate(N, cx, startX, endX);
computeCostForCoordinate(M, cy, startY, endY);
int bestTotalDistance = 0x3f3f3f3f;
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= M; ++j) {
if(!A[i][j] && cx[i] + cy[j] < bestTotalDistance) {
bestTotalDistance = cx[i] + cy[j];
xs = i;
ys = j;
}
}
}
cout << xs << " " << ys << "
";
// printf("Best total disance = %d
", bestTotalDistance);
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2152 Arhipelag
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2152 Arhipelag de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!