== include(page="template/taskheader" task_id="volum") ==
Poveste şi cerinţă...
K.L. 2.0 şi-a dorit o piscină pe un grid A cu $N$ linii şi $M$ coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să îşi niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate (i, j) a gridului are o înalţime <tex> A_i,j</tex> (1 ≤ $i$ ≤ $N$ şi 1 ≤ $j$ ≤ $M$). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.
Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.
h2. Cerinţă
Pentru $N$, $M$ şi gridul A date, să se determine volumul de apă care a rămas în piscină.
h2. Date de intrare
Fişierul de intrare $volum.in$ ...
Fişierul de intrare $volum.in$ conţine pe prima linie două numere naturale $N$ şi $M$, reprezentând dimensiunile gridului, iar pe fiecare dintre următoarele $N$ linii se află câte $M$ numere, reprezentând înălţimile terenului, separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $volum.out$ ...
Fişierul de ieşire $volum.out$ conţine un singur număr, reprezentând volumul de apă care a rămas în piscină.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N, M ≤ 752$
* $0$ $≤$ <tex>A_i,j</tex> $≤$ $10^9^$ $+$ $2$
* Pentru 30% din punctaj, $3 ≤ N, M ≤ 82$.
* Pentru 40% din punctaj, $0$ $≤$ <tex>A_i,j</tex> $≤$ $10^3^$ $+$ $2$.
* Volumul apei este suma unităţilor de apă care rămâne în celulele piscinei.
h2. Exemplu
table(example). |_. volum.in |_. volum.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3
2 2 2
2 0 2
2 2 2
|2
|
|3 3
3 3 3
3 0 2
3 3 3
| 2
|
|5 5
2 2 3 3 3
2 2 3 1 3
2 3 1 3 3
2 2 3 2 2
2 2 2 2 2
|4
|
h3. Explicaţie
...
In primul exemplu rămân după ploaie două unităţi de apă în celula cu înălţimea 0. Nu pot rămâne 3 unităţi, deoarece o unitate s-ar scurge prin una din cele 4 celule vecine în exteriorul piscinei.
In al doilea exemplu rămân după ploaie două unităţi de apă în celula cu înălţimea 0. Nu pot rămâne 3 unităţi, deoarece o unitate s-ar scurge prin celula vecină cu valoarea 2 în exteriorul piscinei.
In al treilea exemplu rămân după ploaie câte două unităţi de apă în celulele cu înălţimea 1. Nu pot rămâne câte 3 unităţi. De exemplu, din celula (2,4) apa se poate scurge în celula (2,5) şi apoi în exterior, respectiv din celula (3,3) în şirul de celule (4,3) - (5,3) şi apoi în exterior.
== include(page="template/taskfooter" task_id="volum") ==
