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

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

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

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