padure

Time limit: 0.2s Memory limit: 64MB Input: padure.in Output: padure.out

Cerință

Harta Țării Dreptunghi este codificată printr-o matrice cu 00 și 11. Valorile 11 delimitează județele, marcând granițele lor. Două elemente 11 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 11: cate județe sunt
  • Întrebare de tipul 22: 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, nn și mm, separate prin spațiu, reprezentând numărul de linii și numărul de coloane ale matricei.
Pe următoarele nn linii se află câte mm elemente, ce pot fi 00 sau 11, neseparate prin spații.
Pe următoatea linie este un număr QQ. Acesta poate fi 11 sau 22, după tipul întrebării la care trebuie să răspundem.
Dacă valoarea este 22, pe linia următoare se mai află încă 44 numere, separate prin spațiu, L1L_1, C1C_1, L2L_2, C2C_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

  • 1n,m1 0001 \leq n, m \leq 1 \ 000;
  • 1L1L2n1 \leq L_1 \leq L_2 \leq n;
  • 1C1C2n1 \leq C_1 \leq C_2 \leq n;
  • Valorile 11 de pe granițe, nu aparțin niciunui județ;
  • Pentru 3131 de puncte nn și mm sunt cel mult egale cu 5050 și Q=1Q=1;
  • Pentru restul de puncte avem Q=2Q=2.

Exemplul 1

padure.in

6 10
0001000010
0000111100
0001000000
1110011111
0000011000
0000010000
1

padure.out

4

Explicație

Sunt 4 județe:

0001000010\textcolor{green}{000}\textcolor{red}{1}\textcolor{blue}{0000}\textcolor{red}{1}\textcolor{yellow}{0}
0000111100\textcolor{green}{0000}\textcolor{red}{1111}\textcolor{yellow}{00}
0001000000\textcolor{green}{000}\textcolor{red}{1}\textcolor{yellow}{000000}
1110011111\textcolor{red}{111}\textcolor{yellow}{00}\textcolor{red}{11111}
0000011000\textcolor{yellow}{00000}\textcolor{red}{11}\textcolor{blue}{000}
0000010000\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,81, 8 și colțul din dreapta jos 4,104, 10, răspunsul este 22 (sunt valori 00 corespunzătoare a două județe):

0001000010\textcolor{green}{000}\textcolor{red}{1}\textcolor{blue}{000}\colorbox{DarkGray}{\textcolor{blue}{0}\textcolor{red}{1}\textcolor{yellow}{0}}
0000111100\textcolor{green}{0000}\textcolor{red}{111}\colorbox{DarkGray}{\textcolor{red}{1}\textcolor{yellow}{00}}
0001000000\textcolor{green}{000}\textcolor{red}{1}\textcolor{yellow}{000}\colorbox{DarkGray}{\textcolor{yellow}{000}}
1110011111\textcolor{red}{111}\textcolor{yellow}{00}\textcolor{red}{11}\colorbox{DarkGray}{\textcolor{red}{111}}
0000011000\textcolor{yellow}{00000}\textcolor{red}{11}\textcolor{blue}{000}
0000010000\textcolor{yellow}{00000}\textcolor{red}{1}\textcolor{blue}{0000}

Log in or sign up to be able to send submissions!