# PBinfo #2436 – castel1 – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț Arheologii au descoperit pe un platou muntos greu accesibil ruinele unui castel medieval, pe care l-au fotografiat din elicopter, obţinând harta digitizată a acestuia. Harta este memorată sub forma unui tablou bidimensional H, compus din N x N pătrate cu latura egală cu unitatea, având ca elemente numere naturale între 0 și 15, care codifică forma pereţilor fiecărui pătrat unitar. Dacă scriem numărul natural H[i][j] în baza 2, folosind exact 4 cifre binare, fiecare bit dă informații despre unul dintre pereții posibil de construit pe fiecare latură a pătratului unitar din poziția (i,j), astfel: dacă bitul de pe poziția 0 are valoarea 1, atunci există perete pe latura vestică (latura din stânga); dacă bitul de pe poziția 1 are valoarea 1, atunci există perete pe latura sudică (latura de jos); dacă bitul de pe poziția 2 are valoarea 1, atunci există perete pe latura estică (latura din dreapta); dacă bitul de pe poziția 3 are valoarea 1, atunci există perete pe latura nordică (latura de sus); un bit de valoare 0 indică lipsa peretelui corespunzător acestuia; Pentru un număr scris în baza 2, numerotarea cifrelor începe cu poziția 0, de la dreapta la stânga. Castelul este interesant deoarece, pentru realizarea unei mai bune apărări, camerele ce-l compun sunt construite fie independent, fie una în interiorul alteia. Orice camera este construită la o distanţă de cel puţin o unitate faţă de zidul ce împrejmuieşte castelul sau faţă de pereţii altor camere. Folosind harta, arheologii doresc să afle informaţii privind numărul camerelor şi camera de arie maximă. Prin arie a unei camere se înţelege numărul pătratelor unitate cuprinse în interiorul pereților aceasteia, fără a socoti ariile camerelor construite în interiorul ei. Cerința Cunoscând codificarea hărţii castelului, să se determine: 1. numărul total al camerelor din castel 2. aria maximă a unei camere 3. coordonatele colţurilor din stânga-sus, respectiv dreapta-jos a camerei cu aria maximă. Dacă există mai multe camere având aceeaşi arie maximă, atunci se vor afişa coordonatele camerei având colţul din stânga-sus (lin1, col1) cu lin1 minimă, iar la linii egale pe aceea cu col1 minimă. Date de intrare Datele de intrare se citesc din fişierul castel1.in, care are următoarea structură: - Pe prima linie se află numărul natural C, care poate fi egal cu 1, 2 sau 3, în funcţie de cerinţa ce trebuie rezolvată; - Pe linia următoare se află numărul natural N, reprezentând dimensiunea hărţii; - Pe următoarele N linii se găsesc câte N numere naturale din intervalul [0,15], separate prin câte un spaţiu, reprezentând harta castelului. Date de ieșire Datele de ieşire se vor scrie în fişierul castel1.out, astfel: - Dacă C = 1, pe prima linie se va scrie numărul total al camerelor din castel; - Dacă C = 2, pe prima linie se va scrie aria maximă a unei camere din castel; - Dacă C = 3, pe prima linie se vor scrie patru numere naturale lin1 col1 lin2 col2, separate prin câte un spaţiu, reprezentând coordonatele colțurilor din stânga-sus, respectiv dreapta-jos ale camerei de arie maximă. Restricții și precizări 2 < n ≤ 100 Se garantează că în castel există cel puţin o cameră; Testele care au C = 1 totalizează 20 de puncte; Testele care au C = 2 totalizează 50 de puncte; Testele care au C = 3 totalizează 20 de puncte; În concurs s-au acordat 10 puncte din oficiu. Aici se vor acorda pentru exemplele din enunț. Exemplul 1: castel1.in 1 9 0 2 0 0 0 0 0 0 0 4 15 1 0 0 2 2 0 0 0 10 2 0 4 11 14 1 0 4 9 12 1 2 10 10 2 0 4 3 6 5 9 8 10 12 1 0 10 8 4 1 4 15 5 1 4 13 1 4 3 2 10 6 1 4 7 1 0 8 8 8 8 0 0 8 0 0 0 0 0 0 0 castel1.out 6 Explicație În figură este reprezentată harta castelului codificat în fișierul de intrare. Acesta conține 6 camere. Exemplul 2: castel1.in 2 9 0 2 0 0 0 0 0 0 0 4 15 1 0 0 2 2 0 0 0 10 2 0 4 11 14 1 0 4 9 12 1 2 10 10 2 0 4 3 6 5 9 8 10 12 1 0 10 8 4 1 4 15 5 1 4 13 1 4 3 2 10 6 1 4 7 1 0 8 8 8 8 0 0 8 0 0 0 0 0 0 0 castel1.out 11 Explicație Aria maximă a unei camere este 11. Exemplul 3: castel1.in 3 9 0 2 0 0 0 0 0 0 0 4 15 1 0 0 2 2 0 0 0 10 2 0 4 11 14 1 0 4 9 12 1 2 10 10 2 0 4 3 6 5 9 8 10 12 1 0 10 8 4 1 4 15 5 1 4 13 1 4 3 2 10 6 1 4 7 1 0 8 8 8 8 0 0 8 0 0 0 0 0 0 0 castel1.out 5 5 7 8 Explicație Camera cu aria maximă are coordonatele (5,5) – (7,8). ## Cod sursă C++ ```cpp #include #include #define Nmax 102 #define Cmax Nmax*Nmax #define InFile "castel1.in" #define OutFile "castel1.out" using namespace std; short A[Nmax][Nmax], Viz[Nmax][Nmax]; short N; short C; short ValBit(short No, short Pos) { return ((1<>Pos; } void Fill(short lin, short col, short &Aria, short &elin, short &ecol) { short i, j; short Clin[Cmax], Ccol[Cmax]; short CrrLin, CrrCol, Prim, Ultim; Aria = 0; elin = lin; ecol = col; Prim = 1; Ultim = 1; Clin[Ultim] = lin; Ccol[Ultim] = col; while(Prim <= Ultim) { CrrLin = Clin[Prim]; CrrCol = Ccol[Prim++]; Viz[CrrLin][CrrCol] = 1; Aria++; if(elin<=CrrLin && ecol<=CrrCol) elin = CrrLin, ecol = CrrCol; if(!ValBit(A[CrrLin][CrrCol], 3) && !Viz[CrrLin-1][CrrCol]) //Nord {Ultim++; Clin[Ultim] = CrrLin-1; Ccol[Ultim] = CrrCol; Viz[CrrLin-1][CrrCol] = 1; } if(!ValBit(A[CrrLin][CrrCol], 2) && !Viz[CrrLin][CrrCol+1]) //Est {Ultim++; Clin[Ultim] = CrrLin; Ccol[Ultim] = CrrCol+1; Viz[CrrLin][CrrCol+1] = 1; } if(!ValBit(A[CrrLin][CrrCol], 1) && !Viz[CrrLin+1][CrrCol]) //Sud {Ultim++; Clin[Ultim] = CrrLin+1; Ccol[Ultim] = CrrCol; Viz[CrrLin+1][CrrCol] = 1; } if(!ValBit(A[CrrLin][CrrCol], 0) && !Viz[CrrLin][CrrCol-1]) //Vest {Ultim++; Clin[Ultim] = CrrLin; Ccol[Ultim] = CrrCol-1; Viz[CrrLin][CrrCol-1] = 1; } } } int main() { int i, j, k; short Slin[Cmax], Scol[Cmax], Svf = 0; short slin, scol, elin, ecol, Aria; short maxil, maxic, maxfl, maxfc, AriaMax=0, NrCamere; ifstream Fin(InFile); //citire Fin >> C >> N; for(i=1;i<=N;i++) for(j=1;j<=N;j++) { Fin >> A[i][j]; if(A[i][j] == 9 || A[i][j] == 11 || A[i][j] == 15 || A[i][j] == 13) { Svf++; Slin[Svf] = i; Scol[Svf] = j; } } Fin.close(); //initializare for(i=0;i<=N+1;i++) { Viz[0][i] = Viz[N+1][i] = 15; Viz[i][0] = Viz[i][N+1] = 15; } for(i=1;i<=N;i++) for(j=1;j<=N;j++) Viz[i][j] = 0; //rezolvare NrCamere = Svf; while(Svf) { slin = Slin[Svf]; scol = Scol[Svf]; Fill(slin, scol,Aria, elin, ecol); Svf--; if(Aria>=AriaMax) maxil = slin, maxic = scol, maxfl = elin, maxfc = ecol, AriaMax = Aria; } ofstream Fou(OutFile); if ( C == 1) Fou<