Editing 2235 - tsunami (section)

= Exemplu: =
<code>tsunami.in</code>
 6 7 3
 0 0 4 2 5 0 0
 1 0 0 7 3 6 0
 2 3 0 5 2 2 0
 0 7 5 4 0 0 0
 0 5 2 3 0 2 0
 0 4 4 8 0 2 0
<code>tsunami.out</code>
 6

=== Explicație ===
Zonele inundate sunt reprezentate îngroşat în tabloul bidimensional:
{| class="wikitable"
|<code>0</code>
|<code>0</code>
|<code>4</code>
|<code>2</code>
|<code>5</code>
|<code>0</code>
|<code>0</code>
|-
|<code>1</code>
|<code>0</code>
|<code>0</code>
|<code>7</code>
|<code>3</code>
|<code>6</code>
|<code>0</code>
|-
|<code>2</code>
|<code>3</code>
|<code>0</code>
|<code>5</code>
|<code>2</code>
|<code>2</code>
|<code>0</code>
|-
|<code>0</code>
|<code>7</code>
|<code>5</code>
|<code>4</code>
|<code>0</code>
|<code>0</code>
|<code>0</code>
|-
|<code>0</code>
|<code>5</code>
|<code>2</code>
|<code>3</code>
|<code>0</code>
|<code>2</code>
|<code>0</code>
|-
|<code>0</code>
|<code>4</code>
|<code>4</code>
|<code>8</code>
|<code>0</code>
|<code>2</code>
|<code>0</code>
|}

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys

def is_valid_land(grid, n, m, i, j):
    """Checks if the given cell (i, j) is a valid land area."""
    if 0 <= i < n and 0 <= j < m:
        return grid[i][j] > 0
    return False

def mark_affected_areas(grid, n, m, h):
    """Marks affected land areas starting from water cells."""
    affected_count = 0
    stack = []

    # Initialize stack with water cells adjacent to land
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 0:
                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    new_i = i + di
                    new_j = j + dj
                    if is_valid_land(grid, n, m, new_i, new_j):
                        stack.append((new_i, new_j))

    # Mark affected land areas using DFS
    while stack:
        i, j = stack.pop()
        if grid[i][j] > 0 and grid[i][j] <= h:
            grid[i][j] = -1  # Mark as affected
            affected_count += 1

            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                new_i = i + di
                new_j = j + dj
                if is_valid_land(grid, n, m, new_i, new_j) and grid[new_i][new_j] > 0:
                    stack.append((new_i, new_j))

    return affected_count

def main():
    """Reads input, marks affected areas, and prints the result."""
    n, m, h = map(int, input().split())

    # Read the grid data
    grid = []
    for _ in range(n):
        row = list(map(int, input().split()))
        grid.append(row)

    # Mark affected land areas and count them
    affected_count = mark_affected_areas(grid, n, m, h)

    # Print the number of affected land areas
    print(affected_count)

if __name__ == "__main__":
    sys.stdin = open("tsunami.in")
    sys.stdout = open("tsunami.out", "w")
    main()
    sys.stdin.close()
    sys.stdout.close()

</syntaxhighlight>