Cod sursa(job #1069731)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 30 decembrie 2013 14:21:43
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>

using namespace std;

int L,C,K,sol,a[155][155];
bool fr[25000],viz[155][155];
int dx[]={-1,0,1, 0};
int dy[]={ 0,1,0,-1};

struct coord
{
    int lin,col;
};
coord Q[1500000];

inline void Read()
{
    int i,j;
    ifstream fin("castel.in");
    fin>>L>>C>>K;
    fr[K]=true;
    for(i=1;i<=L;++i)
        for(j=1;j<=C;++j)
            fin>>a[i][j];
    fin.close();
}

inline bool Ok(int x, int y)
{
    int t,xf,yf;
    for(t=0;t<4;++t)
    {
        xf=x+dx[t]; yf=y+dy[t];
        if(fr[a[xf][yf]] && !viz[xf][yf])
            return true;
    }
    return false;
}

inline void Solve()
{
    int pr,ul,t,x,y,xf,yf;
    pr=ul=1; Q[1].lin=K/C+1; Q[1].col=K%C;
    if(Q[1].col==0)
        Q[1].col=C;
    if(K%C==0)
        --Q[1].col;

    viz[Q[1].lin][Q[1].col]=true; sol=1;
    while(pr<=ul)
    {
        x=Q[pr].lin; y=Q[pr].col; ++pr;
        for(t=0;t<4;++t)
        {
            xf=x+dx[t]; yf=y+dy[t];
            if((fr[a[xf][yf]] && viz[xf][yf] && Ok(xf,yf)) || (fr[a[xf][yf]] && !viz[xf][yf]))
            {
                if(!fr[(xf-1)*C+yf])
                    fr[(xf-1)*C+yf]=true;
                if(!viz[xf][yf])
                    ++sol;
                viz[xf][yf]=true;
                ++ul;
                Q[ul].lin=xf; Q[ul].col=yf;
            }
        }
    }

    ofstream fout("castel.out");
    fout<<sol<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}