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

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