Cod sursa(job #424262)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 24 martie 2010 18:34:28
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>

using namespace std;

int m[155][155];
int lee[155][155];
int camere,req[2][23000];
bool chei[23000];
int pq,uq,maxi,N,M,o;
int qi[23000],qj[23000];
int ii[4]={-1,0,0,1},
    jj[4]={0,-1,1,0};

void do_lee()
{
    o=0;
    int i,j;
    while(pq<uq)
    {
        i=qi[++pq];
        j=qj[pq];
        for(int h=0;h<4;h++)
            if(chei[m[i+ii[h]][j+jj[h]]] && !lee[i+ii[h]][j+jj[h]] )
            {
                camere++;
                maxi=lee[i+ii[h]][j+jj[h]]=lee[i][j]+1;
                chei[(i+ii[h]-1)*N+jj[h]+j]=true;
                qi[++uq]=i+ii[h];
                qj[uq]=j+jj[h];
            }
            else {if((i+ii[h]<=M) && (i+ii[h]>0) && (jj[h]+j<=N) && (jj[h]+j>0) && (!lee[i+ii[h]][j+jj[h]]))
                    {req[0][++o]=i+ii[h];req[1][o]=jj[h]+j;}}
    }
}

void check_req()
{
    for(int i=1;i<=o;i++)
        if(chei[m[req[0][i]][req[1][i]]] && !lee[req[0][i]][req[1][i]])
            qi[++uq]=req[0][i],
            qj[uq]=req[1][i],
            lee[req[0][i]][req[1][i]]=maxi+1,
            camere++;
}

void afis()
{
    for(int i=1;i<=M;i++)
    {
        for(int j=1;j<=N;j++)
            cout<<lee[i][j];
        cout<<endl;
    }
    cout<<endl;
}

int main()
{
    freopen ("castel.in","r",stdin);
    freopen ("castel.out","w",stdout);
    int K,i,j;
    cin>>M>>N>>K;
    chei[K]=1;
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++)
            cin>>m[i][j];

    i=K/N+1;
    j=K%N;
    lee[i][j]=1;
    qi[0]=i,qj[0]=j;
    pq=-1,uq=0;
    camere=1;
    while(pq<uq)
    {
        do_lee();
        check_req();
    }
    //afis();
    cout<<camere;
    return 0;
}