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