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 valoarea1
, atunci există perete pe latura vestică (latura din stânga); - dacă bitul de pe poziția
1
are valoarea1
, atunci există perete pe latura sudică (latura de jos); - dacă bitul de pe poziția
2
are valoarea1
, atunci există perete pe latura estică (latura din dreapta); - dacă bitul de pe poziția
3
are valoarea1
, 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)
.