1117 - Volum

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 Ai,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șierul de intrare volumIN.txt conține pe prima linie două numere naturale N și M, reprezentând dimensiunile grid-ului, 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șierul de ieșire volumOUT.txt 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

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

Exemplul 1:

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.

Exemplul 2:

volumIN.txt

3 3
3 3 3
3 0 2
3 3 3

volumOUT.txt

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.

Exemplul 3:

volumIN.txt

1 3
3 3 3
3 0 2
3 3 3

volumOUT.txt

Datele nu corespund restrictiilor impuse

Exemplul 4:

volumIN.txt

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

volumOUT.txt

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.

Rezolvare

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()