Cod sursa(job #2268829)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 25 octombrie 2018 13:31:49
Problema Castel Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <cstdio>

#include <queue>


using namespace std;


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

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

int a[155][155], fr[22503], nr=1;

int n, m, k;

queue <pair <int, int> >Q;



/**int lee(int k)

{

int x=(k-1)/m+1;

int y=(k-1)%m+1;

fr[k]=1;

a[x][y]=-1;

int ok=0;

Q.push(make_pair(x, y));

while(!Q.empty())

{

pair<int, int> p=Q.front();

Q.pop();

for(int i=0; i<4; i++)

{

int c=(p.first+di[i]-1)*m+p.second+dj[i];

if(a[p.first+di[i]][p.second+dj[i]]!=-1 && fr[a[p.first+di[i]][p.second+dj[i]]]>0)

{

if(fr[c]==0)

{

ok=1;

fr[c]=1;

nr++;

}

a[p.first+di[i]][p.second+dj[i]]=-1;

Q.push(make_pair(p.first+di[i], p.second+dj[i]));

continue;

}

}

}

return ok;

}**/


int lee(int k)

{

    int x=(k-1)/m+1;

    int y=(k-1)%m+1;

    fr[k]=1;

    a[x][y]=-1;

    Q.push(make_pair(x, y));

    int ok=0;

    while(!Q.empty())

    {

        int i=Q.front().first;

        int j=Q.front().second;

        Q.pop();

        for(int v=0; v<4; v++)

        {

            int iv=i+di[v];

            int jv=j+dj[v];

            int c=(iv-1)*m+jv;

            if(a[iv][jv]!=-1 && fr[a[iv][jv]]>0)

            {

                if(fr[c]==0)

                {

                    ok=1;

                    fr[c]=1;

                    nr++;

                }

                a[iv][jv]=-1;

                Q.push(make_pair(iv, jv));

                continue;

            }

        }

    }

    return ok;

}


void border()

{

    for(int i=1; i<=n; i++)

    {

        a[i][0]=-1;

        a[i][m+1]=-1;

    }

    for(int j=1; j<=m; j++)

    {

        a[0][j]=-1;

        a[n+1][j]=-1;

    }

}




void zerozare()

{

    for(int i=1; i<=n; i++)

        for(int j=1; j<=m; j++)

            if(a[i][j]==-1)

                a[i][j]=0;

}


int main()

{

    freopen("castel.in", "r", stdin);

    freopen("castel.out", "w", stdout);

    scanf("%d %d %d", &n, &m, &k);

    for(int i=1; i<=n; i++)

        for(int j=1; j<=m; j++)

            scanf("%d ", &a[i][j]);

    fr[0]=1;

    border();

    while(lee(k))

    {

        zerozare();

    }

    printf("%d", nr);


    return 0;

}