Cod sursa(job #1069793)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 30 decembrie 2013 15:12:54
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

inline void Solve()
{
    int pr,ul,t,x,y,xf,yf,n,i;
    ofstream fout("castel.out");
    pr=ul=1;
    Q[1]=K; viz[K/C][K%C]=true;
    while(pr<=ul)
    {
        n=Q[pr]; fr[n]=true;
        ++pr; ++sol;
        for(i=0;i<Lista[n].size();++i)
            if(!viz[Lista[n][i]/C][Lista[n][i]%C])
            {
                Q[++ul]=Lista[n][i];
                viz[Lista[n][i]/C][Lista[n][i]%C]=true;
            }

        x=n/C; y=n%C;
        for(t=0;t<4;++t)
        {
            xf=x+dx[t]; yf=y+dy[t];
            if(xf<0 || yf<0 || xf>=L || yf>=C || viz[xf][yf])
                continue;
            if(fr[a[xf][yf]])
            {
                Q[++ul]=xf*C+yf;
                viz[xf][yf]=true;
            }
            else
                Lista[a[xf][yf]].push_back(xf*C+yf);
        }
    }
    fout<<sol<<"\n";
    fout.close();
}

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