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

<syntaxhighlight lang="python" line>

1. 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]

1. 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)]

1. Calcularea volumului de apă rămas în piscină

result = volum_apa(N, M, A)

1. Scrierea rezultatului în fișierul "volumout.txt"

with open("volumout.txt", "w") as file:

   file.write(str(result))

</syntaxhighlight>