| Fişierul intrare/ieşire: | castel3.in, castel3.out | Sursă | OJI 2018, Clasa a 10-a |
| Autor | Alin Burta | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Castel3
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 NxN 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);
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:
- numărul total al camerelor din castel
- aria maximă a unei camere
- 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 castel3.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 castel3.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 4 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
- 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;
- Conform regulamentului OJI, se acordă 10 puncte pentru exemple.
Exemplu
| castel3.in | castel3.out | Explicaţie |
|---|---|---|
| 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 | 6 | În figură este reprezentată harta castelului codificat în fişierul de intrare. Acesta conţine 6 camere. 
|
| 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 | 11 | Aria maximă a unei camere este 11. |
| 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 | 5 5 7 8 | Camera cu aria maximă are coordonatele (5,5) - (7,8). |
