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

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`

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema tsunami:

/*
    Eugen Nodea
    Implementare - fill pe coada
*/

# include <cstdio>
# include <queue>
# define nmax 1002
# define mmax 1002
using namespace std;

// evident ca se poate renunta la o matrice
int n,m,h,A[nmax][mmax],i,j,M[nmax][mmax],ic,jc,sol,x,y,k;

int dx[] = {0, 1, 0,-1};
int dy[] = {1, 0,-1, 0};

typedef pair<short int, short int> celula;
queue <celula> q;

//Verfific daca un patrat este adiacent cu o zona de apa
inline int vecini(int i, int j)
{
    int k,x,y;
    for (k=0; k<4; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (A[x][y]==0) return 1;
        }
    return 0;
}
//construim coada cu patrate adiacente cu patrate indundate
void add(int i, int j)
{
    int k,x,y;
    for (k=0; k<4; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (A[x][y] != A[i][j] && A[x][y] > 0 && A[x][y] < h && M[x][y] == 0)
            {
                q.push(make_pair(x, y));
            }
        }
}

void fill(int i, int j)
{
    int k,x,y;
    M[i][j] = h - A[i][j];
    ++sol;
    add(i,j);
    for (k=0; k<4; ++k)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (A[i][j] == A[x][y] && M[x][y] == 0) fill(x,y);
        }
}

int main(){

    freopen("tsunami.in", "r", stdin);
    freopen("tsunami.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &h);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            scanf ("%d ",&A[i][j]);
    //bordez matricea
    for (i=0; i<=n+1; ++i)
    {
        A[i][0] = A[i][m+1] = -1;
    }
    for (i=0; i<=m+1; ++i)
    {
        A[0][i] = A[n+1][i] = -1;
    }

    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            if (A[i][j] < h && M[i][j] == 0 && A[i][j] > 0)
                if (vecini(i,j)) fill(i,j);

    while (!q.empty())
    {
        ic = q.front().first; jc = q.front().second;
        if (M[ic][jc] == 0) fill(ic,jc);
        q.pop();
    }


    printf("%d\n", sol);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2235 tsunami

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2235 tsunami de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2235 tsunami