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:

#include <bits/stdc++.h>

using namespace std;

ifstream cin("tsunami.in");
ofstream cout("tsunami.out");

int a[1001][1001] , b[1001][1001] , n , m;
struct shen
{
    int i , j;
};

int inside(int i , int j)
{
    return i<=n && i>= 1 && j <= m && j >= 1;
}

queue<shen> Q;

int di[]={1 , 0 , -1 , 0};
int dj[]={0 , 1 , 0 , -1};

void lee(int x , int y)
{
    shen p;
    p.i=x , p.j=y;
    Q.push(p);
    while(!Q.empty())
    {
        p.i=Q.front().i;
        p.j=Q.front().j;
        for(int k = 0 ; k <= 3 ; ++k)
        {
            int inou=p.i+di[k];
            int jnou=p.j+dj[k];
            if(inside(inou,jnou) && b[inou][jnou]==0)
            {
                shen pnou;
                pnou.i=inou;
                pnou.j=jnou;
                Q.push(pnou);
                b[inou][jnou]=2;
            }
        }
        Q.pop();
    }
}


int main()
{
    int k;
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
        {
            cin >> a[i][j];
            if(a[i][j]<k)
                b[i][j]=0;
            else
                b[i][j]=1;
        }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j]==0)
                lee(i , j);
    int cnt=0;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            if(a[i][j]!=0 && b[i][j]==2)
                cnt++;
        }
    }
    cout << cnt;
    return 0;
}