== include(page="template/taskheader" task_id="castel3") ==
Poveste şi cerinţă...
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.
h2. 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ă.
h2. Date de intrare
Fişierul de intrare $castel3.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $castel3.out$ ...
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ă.
h2. 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.
h2. Exemplu
table(example). |_. castel3.in |_. castel3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. 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.
!>problema/castel3?exemplu.png!
|
h3. Explicaţie
...
|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)$.
|
== include(page="template/taskfooter" task_id="castel3") ==
