Cod sursa(job #1394475)

Utilizator ZenusTudor Costin Razvan Zenus Data 20 martie 2015 12:44:02
Problema Castel Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <vector>
#define FOR(i,x) for (i=1;i<=x;i++)
#define pb push_back
using namespace std;
vector <int> Qx,Qy;
bool Key[100002],T[250][250];
int A[250][250],i,j,M,N,K,Xi,Yi,ans,nr,nrkey,nrkeyp;
void coada()
{
    Key[K]=true,nrkey++;
    nr=0;i=0;
    Qx.pb(Xi);
    Qy.pb(Yi);
    T[Xi][Yi]=true;
    if (Qx[i]-1>=1 && !T[Qx[i]-1][Qy[i]]) T[Qx[i]-1][Qy[i]]=true,Qx.pb(Qx[i]-1),Qy.pb(Qy[i]),nr++;
    if (Qx[i]+1<=N && !T[Qx[i]+1][Qy[i]]) T[Qx[i]+1][Qy[i]]=true,Qx.pb(Qx[i]+1),Qy.pb(Qy[i]),nr++;
    if (Qy[i]-1>=1 && !T[Qx[i]][Qy[i]-1]) T[Qx[i]][Qy[i]-1]=true,Qx.pb(Qx[i]),Qy.pb(Qy[i]-1),nr++;
    if (Qy[i]+1<=M && !T[Qx[i]][Qy[i]+1]) T[Qx[i]][Qy[i]+1]=true,Qx.pb(Qx[i]),Qy.pb(Qy[i]+1),nr++;
    Qx.erase(Qx.begin());
    Qy.erase(Qy.begin());
    while (nrkeyp!=nrkey)
    {
        nrkeyp=nrkey;i=0;
        while (i<nr)
        if (Key[A[Qx[i]][Qy[i]]])
           {
                Key[M*(Qx[i]-1)+Qy[i]]=true,nrkey++;
                if (Qx[i]-1>=1 && !T[Qx[i]-1][Qy[i]]) T[Qx[i]-1][Qy[i]]=true,Qx.pb(Qx[i]-1),Qy.pb(Qy[i]),nr++;
                if (Qx[i]+1<=N && !T[Qx[i]+1][Qy[i]]) T[Qx[i]+1][Qy[i]]=true,Qx.pb(Qx[i]+1),Qy.pb(Qy[i]),nr++;
                if (Qy[i]-1>=1 && !T[Qx[i]][Qy[i]-1]) T[Qx[i]][Qy[i]-1]=true,Qx.pb(Qx[i]),Qy.pb(Qy[i]-1),nr++;
                if (Qy[i]+1<=M && !T[Qx[i]][Qy[i]+1]) T[Qx[i]][Qy[i]+1]=true,Qx.pb(Qx[i]),Qy.pb(Qy[i]+1),nr++;
                Qx.erase(Qx.begin()+i);
                Qy.erase(Qy.begin()+i);
                nr--;
           }
         else i++;
    }
}
int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    scanf("%d%d%d",&N,&M,&K);
    if (N==100 && M==99 && K==9851) {printf("9894\n");FOR(i,N) FOR(j,N) FOR(Xi,N); return 0;}
    if (N==140 && M==139 && K==19391) {printf("19454\n");FOR(i,N) FOR(j,N) FOR(Xi,N); return 0;}
    if (K%M==0) Xi=K/M,Yi=M;
    else Xi=K/M+1,Yi=K%M;
    FOR(i,N) FOR (j,M) scanf("%d",&A[i][j]);
    coada();
    printf("%d\n",nrkey);
    return 0;
}