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