Cod sursa(job #1870614)

Utilizator GoogalAbabei Daniel Googal Data 6 februarie 2017 19:40:14
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <vector>
#include <queue>
#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");

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 < int, int > > coada[nmax * nmax];

queue < pair < int , int > > coadalee;

inline void cit( 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()
{
    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();
}

inline bool ok(int x, int y)
{
    if(x<1 || y<1 || x>n || y>m || viz[x][y]!=2)
        return false;
    return true;
}

void solve(int key)
{
    int i;
    for(i=0;i<coada[key].size();i++)
    {
        int x=coada[key][i].first,y=coada[key][i].second;
        viz[x][y]=2;
        if(!ekey[c[x][y]])
        {
            ekey[c[x][y]]=true;
            solve(c[x][y]);
        }
    }
}

void lee()
{
    int x,y,x_urm,y_urm;
    viz[si][sj]=1;
    rez=1;
    coadalee.push(make_pair(si,sj));
    while(!coadalee.empty())
    {
        x=coadalee.front().first;
        y=coadalee.front().second;
        coadalee.pop();
        for(int dir=0;dir<4;dir++)
        {
            x_urm=x+dx[dir];
            y_urm=y+dy[dir];
            if(ok(x_urm,y_urm))
            {
                viz[x_urm][y_urm]=1;
                rez++;
                coadalee.push(make_pair(x_urm,y_urm));
            }
        }
    }
}

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