== include(page="template/taskheader" task_id="camere") ==
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?”.
Poveste şi cerinţă...
h2. Date de intrare
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).$
Fişierul de intrare $camere.in$ ...
h2. Date de ieşire
Î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.
În fişierul de ieşire $camere.out$ ...
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 |
|5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6
|12
8
6
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
