Cod sursa(job #1870365)

Utilizator GoogalAbabei Daniel Googal Data 6 februarie 2017 16:50:52
Problema Castel Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <fstream>
#include <queue>
#include <vector>
#define hg 1<<10
#define verf ++poz == hg ? fin.read (ch, hg), poz = 0 : 0
#define nmax 151

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

short int n,m,k,c[nmax][nmax],a[nmax][nmax],rez,poz;
bool ekey[nmax*nmax];
char ch[hg];

short int viz[nmax][nmax],si,sj;
short int dx[]= {-1,1,0,0};
short int dy[]= {0,0,-1,1};

vector < pair < short int, short int > > coada[nmax * nmax];

inline void cit( short int &x )
{
    if (ch[0] == '\0') fin.read (ch, hg) ;
    else for (; ch[poz] < '0' || ch[poz] > '9' ; verf) ;
    for (x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' ; x = x * 10 + ch[poz] - '0', verf) ;
}

void read()
{
    short int i,j;
    cit(n);cit(m);cit(k);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            cit(a[i][j]);
            coada[a[i][j]].push_back(make_pair(i,j));
            c[i][j]=(i-1)*m+j;
            if(c[i][j]==k)
            {
                si=i;
                sj=j;
            }
        }
    }
    fin.close();
}

bool vecin(short int x,short int y)
{
    if(viz[x][y]==1)
        return true;
    for(int dir=0; dir<4; dir++)
    {
        if(viz[x+dx[dir]][y+dy[dir]]==1)
            return true;
    }
    return false;
}

void lee(short int x, short int y, queue < short int > &coadalee)
{
    if(ekey[a[x][y]])
    {
        if(!viz[x][y])
            viz[x][y]=2;
        if(vecin(x,y))
        {
            if(viz[x][y]!=1)
            {
                rez++;
                viz[x][y]=1;
                for(short int dir=0;dir<4;dir++)
                {
                    if(viz[x+dx[dir]][y+dy[dir]]==2 && ekey[a[x+dx[dir]][y+dy[dir]]])
                        coadalee.push(a[x+dx[dir]][y+dy[dir]]);
                }
            }
            if(!ekey[c[x][y]] )
            {
                coadalee.push(c[x][y]);
                ekey[c[x][y]]=true;
            }
        }
    }
}


void fillk(short int key)
{
    short int i;
    queue < short int > coadalee;
    for(i=0; i<coada[key].size(); i++)
    {
        lee(coada[key][i].first, coada[key][i].second,coadalee);
    }
    while(!coadalee.empty())
    {
        fillk(coadalee.front());
        coadalee.pop();
    }
}
void solve()
{
    ekey[k]=true;
    viz[si][sj]=1;
    rez=1;
    fillk(k);
}

int main()
{
    read();
    solve();
    fout<<rez;
    fout.close();
    return 0;
}