2235 - tsunami

Tsunamiul este valul mareic ce se propagă prin apa oceanelor/mărilor, ca urmare a producerii unor erupţii subacvatice sau/şi a unor cutremure submarine sau de coastă foarte puternice.

Cercetătorii doresc să preîntâmpine efectele unor posibile valuri mareice prin marcarea şi clasificarea zonelor al căror risc de inundare este ridicat.

Teritoriul studiat a fost împărţit în n×m pătrate identice (zone) rezultând o hartă digitizată, reprezentată sub forma unui tablou bidimensional cu n linii şi m coloane, fiecare element al tabloului memorând cota (înălţimea) terenului din pătratul unitate corespunzător. Zonele de apă au cota 0, iar zonele de uscat au cote mai mari decât 0.

Orice tsunami este clasificat în funcţie de înălţimea valului mareic, pe o scară de la 1 la 10. Cercetătorii doresc să marcheze zonele de risc ce pot fi afectate de un potenţial tsunami.

Iniţial, valul mareic apare în toate zonele de cotă 0 vecine cu cel puţin o zonă de uscat. O zonă teritorială poate fi afectată dacă are cota strict mai mică decât înălţimea valului mareic şi se află în vecinătatea apei sau în vecinătatea unei zone afectate. Două pătrate unitate se învecinează dacă au o latură comună.

Cerința

Dată fiind harta digitizată a zonelor monitorizate, să se determine numărul zonelor de uscat afectate de un tsunami de înălțime h.

Date de intrare

Fișierul de intrare tsunami.in conține pe prima linie trei numere naturale n, m şi h separate prin câte un spațiu, reprezentând dimensiunile hărții, respectiv înălțimea valului mareic. Pe următoarele n linii sunt scrise câte m numere naturale separate prin câte un spațiu reprezentând, în ordine, cotele din cele n×m pătrate teritoriale unitate ale hărții.

Date de ieșire

Fișierul de ieșire tsunami.out conţine o singură valoare ce reprezintă numărul pătratelor unitate afectate de un tsunami de înălţime h.

Restricții și precizări

• 2 ≤ n,m ≤ 1000
• 1 ≤ h ≤ 10
• Zona monitorizată nu conţine lacuri interioare (pătrate unitate învecinate, având cota 0, înconjurate complet de pătrate unitate având cote strict mai mari decît 0)
• Cotele sunt numere naturale ≤ 1000

Exemplu:

tsunami.in

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

tsunami.out

6

Explicație

Zonele inundate sunt reprezentate îngroşat în tabloul bidimensional:

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

Rezolvare

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