== include(page="template/taskheader" task_id="camere") ==
Poveste şi cerinţă...
Se dă o matrice de $N$ linii şi $M$ coloane care conţine numai litere mici ale alfabetului englez. Se defineşte o cameră ca o zonă maximală de celule din matrice ce conţin aceeaşi literă, conexă pe cele $4$ direcţii: sus, jos, stânga, dreapta.
Ne interesează răspunsuri la întrebări de forma: “Câte camere sunt incluse complet sau parţial într-un dreptunghi dat, văzut ca o submatrice?”.
h2. Date de intrare
Fişierul de intrare $camere.in$ ...
Pe prima linie a fişierului de intrare $camere.in$ se vor afla $2$ numere $N$ şi $M$ separate prin câte un spaţiu, iar pe următoarele $N$ linii câte $M$ caractere din alfabetul englez (neseparate prin spaţii). Linia $N+2$ va conţine un număr $Q$, reprezentând numărul de întrebări, iar următoarele $Q$ linii vor conţine câte $4$ numere $x1, y1, x2, y2$ separate prin câte un spaţiu, reprezentând câte un dreptunghi definit prin punctele diagonal opuse de coordonate $(x1,y1)$ şi $(x2,y2).$
h2. Date de ieşire
În fişierul de ieşire $camere.out$ ...
În fişierul de ieşire $camere.out$ se vor afla $Q$ numere pe câte un rând, ce reprezintă răspunsurile la întrebări în ordinea în care au fost date în fişierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N,M ≤ 2000$
* $1 ≤ Q ≤ 5000$
* $1 ≤ x1 ≤ x2 ≤ N$
* $1 ≤ y1 ≤ y2 ≤ M$
* Pentru $70$ de puncte din cele $130$ de puncte se garantează că orice cameră poate fi inclusă complet în orice dreptunghi de query (adică orice cameră se poate translata astfel încât să fie în interiorul dreptunghiului respectiv).
h2. Exemplu
table(example). |_. camere.in |_. camere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6
|12
8
6
|
h3. Explicaţie
...
Avem $3$ întrebări
Întrebarea $1 1 5 6$ se referă la toată matricea, care are $12$ camere.
Dreptunghiul $2 1 4 5$ conţine $8$ camere, dintre care $4$ sunt complete şi alte $4$ sunt incomplete.
Dreptunghiul $3 3 5 6$ conţine $6$ camere, dintre care $5$ sunt complete şi o cameră este incompletă.
== include(page="template/taskfooter" task_id="camere") ==
