Oros Ioana Diana at 07:39, 18 May 2024

2024-05-18T07:39:03Z

Oros Ioana Diana: Pagină nouă: 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...

2024-01-08T22:50:36Z

Pagină nouă: 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...

New page

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ța ==
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ă.
== 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 ==
; volumin.txt
: 3 3
: 2 2 2
: 2 0 2
: 2 2 2
; volum.out
: 2
<br>
== Explicatie ==
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
<br>
== Explicatie ==
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.
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1117 - Volum
def volum_apa(N, M, A):
if not (3 <= N <= 752 and 3 <= M <= 752):
return "Fals"

for i in range(N):
for j in range(M):
if not (0 <= A[i][j] <= 109 + 2):
return "Fals"

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def bfs(i, j):
queue = [(i, j)]
visited[i][j] = True

while queue:
x, y = queue.pop(0)

for dx, dy in directions:
nx, ny = x + dx, y + dy

if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
if A[nx][ny] < A[i][j]:
water_volume[0] += A[i][j] - A[nx][ny]
queue.append((nx, ny))
visited[nx][ny] = True

water_volume = [0]
visited = [[False] * M for _ in range(N)]

for i in range(N):
bfs(i, 0)
bfs(i, M - 1)

for j in range(M):
bfs(0, j)
bfs(N - 1, j)

return water_volume[0]

# Citirea datelor de intrare din fișierul "volumin.txt"
with open("volumin.txt", "r") as file:
N, M = map(int, file.readline().split())
A = [list(map(int, file.readline().split())) for _ in range(N)]

# Calcularea volumului de apă rămas în piscină
result = volum_apa(N, M, A)

# Scrierea rezultatului în fișierul "volumout.txt"
with open("volumout.txt", "w") as file:
file.write(str(result))

</syntaxhighlight>

1117 - Volum - Revision history

Oros Ioana Diana at 07:39, 18 May 2024