Editing 1117 - Volum

K.L. 2.0 și-a dorit o piscină pe un grid <code>A</code> cu <code>N</code> linii și <code>M</code> 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 <code>(i, j)</code> a gridului are o înalțime <code>Ai,j</code> (<code>1 ≤ i ≤ N</code> și <code>1 ≤ j ≤ M</code>). 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 <code>N</code>, <code>M</code> și gridul <code>A</code> date, să se determine volumul de apă care a rămas în piscină.

= Date de intrare =
Fișierul de intrare <code>volumIN.txt</code> conține pe prima linie două numere naturale <code>N</code> și <code>M</code>, reprezentând dimensiunile grid-ului, iar pe fiecare dintre următoarele <code>N</code> linii se află câte <code>M</code> numere, reprezentând înălțimile terenului, separate prin câte un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>volumOUT.txt</code> va conține un singur număr, reprezentând volumul de apă care a rămas în piscină. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>3 ≤ N, M ≤ 752</code>
* <code>0 ≤ Ai,j ≤ 109 + 2</code>
* Pentru 30% din punctaj, <code>3 ≤ N, M ≤ 82</code>.
* Pentru 40% din punctaj, <code>0 ≤ Ai,j ≤ 103 + 2</code>.
* Volumul apei este suma unităţilor de apă care rămâne în celulele piscinei.

= Exemplul 1: =
<code>volum.in</code>
 3 3
 2 2 2
 2 0 2
 2 2 2
<code>volum.out</code>
 2

= Explicație =
După ploaie rămân două unități de apă în celula cu înălțimea <code>0</code>. Nu pot rămâne <code>3</code> unități, deoarece o unitate s-ar scurge prin una din cele 4 celule vecine în exteriorul piscinei.

= Exemplul 2: =
<code>volumIN.txt</code>
 3 3
 3 3 3
 3 0 2
 3 3 3
<code>volumOUT.txt</code>
 2

= Explicație =
După ploaie rămân două unități de apă în celula cu înălțimea <code>0</code>. Nu pot rămâne <code>3</code> unități, deoarece o unitate s-ar scurge prin celula vecină cu valoarea <code>2</code> în exteriorul piscinei.

== Exemplul 3: ==
<code>volumIN.txt</code>
 1 3
 3 3 3
 3 0 2
 3 3 3
<code>volumOUT.txt</code>
 Datele nu corespund restrictiilor impuse

= Exemplul 4: =
<code>volumIN.txt</code>
 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
<code>volumOUT.txt</code>
 4

= Explicație =
După ploaie rămân câte două unități de apă în celulele cu înălțimea <code>1</code>. Nu pot rămâne câte <code>3</code> unități. De exemplu, din celula <code>(2,4)</code> apa se poate scurge în celula <code>(2,5)</code> şi apoi în exterior, respectiv din celula <code>(3,3)</code> în şirul de celule <code>(4,3) - (5,3)</code> şi apoi în exterior.

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
import heapq

maxn = 755
n, m = 0, 0
v = [[0] * maxn for _ in range(maxn)]
f = [[0] * maxn for _ in range(maxn)]
sol = 0
hp = []
d1 = [0, 0, -1, 1]
d2 = [1, -1, 0, 0]

def add_element(x, y, h):
    global sol
    if x <= 0 or y <= 0 or x > n or y > m:
        return
    if f[x][y] == 1:
        return

    if h < v[x][y]:
        h = v[x][y]
    sol += h - v[x][y]

    heapq.heappush(hp, (h, x, y))
    f[x][y] = 1

def check_constraints():
    if not (3 <= n <= 752 and 3 <= m <= 752):
        return False
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if not (0 <= v[i][j] <= 10**9 + 2):
                return False
    return True

def main():
    global n, m, sol

    with open("volumIN.txt", "r") as fin:
        n, m = map(int, fin.readline().split())
        for i in range(1, n + 1):
            v[i][1:m + 1] = map(int, fin.readline().split())

    if not check_constraints():
        with open("volumOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return

    for i in range(1, n + 1):
        add_element(i, 1, v[i][1])
        add_element(i, m, v[i][m])
    for j in range(1, m + 1):
        add_element(1, j, v[1][j])
        add_element(n, j, v[n][j])

    while len(hp) > 0:
        hc, xc, yc = heapq.heappop(hp)

        for i in range(4):
            add_element(xc + d1[i], yc + d2[i], hc)

    with open("volumOUT.txt", "w") as fout:
        fout.write(f"{sol}\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>