Problem #228

volum

Time limit: 0.2s
Memory limit: 32MB
Input: volum.in
Output: volum.out

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 \(A_{i,j}\) (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.

Cerință

Pentru N, M și gridul A date, să se determine volumul de apă care a rămas în piscină.

Date de intrare

Fișierului 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.

Date de ieșire

Fișierului de ieșire volum.out conține un singur număr, reprezentând volumul de apă care a rămas în piscină.

Restricții

  • 3 ≤ N, M ≤ 752
  • \(0 ≤ A_{i,j} ≤ 10^9 + 2\)
  • Pentru 30% din punctaj, 3 ≤ N, M ≤ 82.
  • Pentru 40% din punctaj, \(0 ≤ A_{i,j} ≤ 10^3 + 2\).
  • Volumul apei este suma unităţilor de apă care rămâne în celulele piscinei.

Exemplu

volum.in

3 3
2 2 2
2 0 2
2 2 2

volum.out

2

Explicație

După ploaie rămân 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.

volum.in

3 3
3 3 3
3 0 2
3 3 3

volum.out

2

Explicație

După ploaie rămân 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.

volum.in

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

volum.out

4 

Explicație

După ploaie rămân 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.

General info

Uploader: liviu

Author: Radu Voroneanu

Source: ONI 2014 XI-XII: Ziua 1 Problema 3

Submissions