Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Seniori
9 decembrie 2023
Cerință
Harta Țării Dreptunghi este codificată printr-o matrice cu și . Valorile delimitează județele, marcând granițele lor. Două elemente vecine pe aceeași linie, coloană sau diagonală se consideră vecine și pe graniță.
Trebuie să răspundem la două tipuri de întrebări:
- Întrebare de tipul : cate județe sunt
- Întrebare de tipul : se dă o zonă sub formă de dreptunghi (submatrice) unde trebuie înființată o pădure. Trebuie să spunem câte județe au pe teritoriul lor o parte din pădure.
Date de intrare
Pe prima linie a fișierului padure.in
se află două numere, și , separate prin spațiu, reprezentând numărul de linii și numărul de coloane ale matricei.
Pe următoarele linii se află câte elemente, ce pot fi sau , neseparate prin spații.
Pe următoatea linie este un număr . Acesta poate fi sau , după tipul întrebării la care trebuie să răspundem.
Dacă valoarea este , pe linia următoare se mai află încă numere, separate prin spațiu, , , , reprezentând linia și coloana colțului stânga sus, respectiv linia și coloana colțului dreapta jos.
Date de ieșire
Fișierul padure.out
va conține un singur număr, reprezentând răspunsul la întrebarea dată în fișierul de intrare.
Restricții și precizări
- ;
- ;
- ;
- Valorile de pe granițe, nu aparțin niciunui județ;
- Pentru de puncte și sunt cel mult egale cu și ;
- Pentru restul de puncte avem .
Exemplul 1
padure.in
6 10
0001000010
0000111100
0001000000
1110011111
0000011000
0000010000
1
padure.out
4
Explicație
Sunt 4 județe:
Exemplul 2
padure.in
6 10
0001000010
0000111100
0001000000
1110011111
0000011000
0000010000
2
1 8 4 10
padure.out
2
Explicație
Dacă se dă dreptunghiul cu colțul stânga sus și colțul din dreapta jos , răspunsul este (sunt valori corespunzătoare a două județe):