padure

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 $0$ și $1$. Valorile $1$ delimitează județele, marcând granițele lor. Două elemente $1$ 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 $1$: cate județe sunt
• Întrebare de tipul $2$: 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, $n$ și $m$, separate prin spațiu, reprezentând numărul de linii și numărul de coloane ale matricei.
Pe următoarele $n$ linii se află câte $m$ elemente, ce pot fi $0$ sau $1$, neseparate prin spații.
Pe următoatea linie este un număr $Q$. Acesta poate fi $1$ sau $2$, după tipul întrebării la care trebuie să răspundem.
Dacă valoarea este $2$, pe linia următoare se mai află încă $4$ numere, separate prin spațiu, $L_1$, $C_1$, $L_2$, $C_2$ 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

• $1 \leq n, m \leq 1 \ 000$;
• $1 \leq L_1 \leq L_2 \leq n$;
• $1 \leq C_1 \leq C_2 \leq n$;
• Valorile $1$ de pe granițe, nu aparțin niciunui județ;
• Pentru $31$ de puncte $n$ și $m$ sunt cel mult egale cu $50$ și $Q=1$;
• Pentru restul de puncte avem $Q=2$.

Exemplul 1

padure.in

6 10
0001000010
0000111100
0001000000
1110011111
0000011000
0000010000
1

padure.out

4

Explicație

Sunt 4 județe:

$\textcolor{green}{000}\textcolor{red}{1}\textcolor{blue}{0000}\textcolor{red}{1}\textcolor{yellow}{0}$
$\textcolor{green}{0000}\textcolor{red}{1111}\textcolor{yellow}{00}$
$\textcolor{green}{000}\textcolor{red}{1}\textcolor{yellow}{000000}$
$\textcolor{red}{111}\textcolor{yellow}{00}\textcolor{red}{11111}$
$\textcolor{yellow}{00000}\textcolor{red}{11}\textcolor{blue}{000}$
$\textcolor{yellow}{00000}\textcolor{red}{1}\textcolor{blue}{0000}$

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 $1, 8$ și colțul din dreapta jos $4, 10$, răspunsul este $2$ (sunt valori $0$ corespunzătoare a două județe):

$\textcolor{green}{000}\textcolor{red}{1}\textcolor{blue}{000}\colorbox{DarkGray}{\textcolor{blue}{0}\textcolor{red}{1}\textcolor{yellow}{0}}$
$\textcolor{green}{0000}\textcolor{red}{111}\colorbox{DarkGray}{\textcolor{red}{1}\textcolor{yellow}{00}}$
$\textcolor{green}{000}\textcolor{red}{1}\textcolor{yellow}{000}\colorbox{DarkGray}{\textcolor{yellow}{000}}$
$\textcolor{red}{111}\textcolor{yellow}{00}\textcolor{red}{11}\colorbox{DarkGray}{\textcolor{red}{111}}$
$\textcolor{yellow}{00000}\textcolor{red}{11}\textcolor{blue}{000}$
$\textcolor{yellow}{00000}\textcolor{red}{1}\textcolor{blue}{0000}$