Cod sursa(job #1842058)

Utilizator silkMarin Dragos silk Data 6 ianuarie 2017 14:22:55
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <vector>
#define VMax 22500
#define NMax 150
#define x first
#define y second
using namespace std;

typedef pair<int, int> abc;
vector<abc> v[VMax+1];
abc COADA[VMax+1];

char deja[NMax+2][NMax+2];
char key[VMax+1];
int a[NMax+1][NMax+1];
int N,M;

int dirx[4]={1,0,-1,0};
int diry[4]={0,1,0,-1};

void Limits()
{
    for(int i = 0; i <= N+1; ++i) deja[i][0] = deja[i][M+1] = 1;
    for(int i = 0; i <= M+1; ++i) deja[0][i] = deja[N+1][i] = 1;
}

int main(){
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);

    int i,j,k,inc,sf,K,x0,y0,x,y,now,res=0;
    abc temp;

    scanf("%d %d %d",&N,&M,&K);
    for(i = 1; i <= N; ++i)
        for(j = 1; j <= M; ++j) scanf("%d",&a[i][j]);
    Limits();

    x0 = (K-1)/M + 1;
    y0 = (K%M ? K%M : M);
    inc = sf = 0;
    COADA[0].x = x0;
    COADA[0].y = y0;
    key[ a[x0][y0] ] = deja[x0][y0] = 1;
    if( a[x0][y0] != (x0-1)*M + y0 ) { printf("0\n"); return 0; }
    while(inc <= sf)
    {
        ++res;
        x0 = COADA[inc].x;
        y0 = COADA[inc++].y;
        now = (x0-1)*M + y0;
        key[now] = 1;
        while( !v[now].empty() )
        {
            temp = v[now].back();
            v[now].pop_back();
            COADA[++sf].x = temp.x;
            COADA[sf].y = temp.y;
        }

        for(k = 0; k < 4; ++k)
        {
            x = x0 + dirx[k];
            y = y0 + diry[k];
            if( !deja[x][y] )
            {
                if( key[ a[x][y] ] ){
                    COADA[++sf].x = x;
                    COADA[sf].y = y;
                } else {
                    temp.x = x;
                    temp.y = y;
                    v[ a[x][y] ].push_back(temp);
                }
                deja[x][y] = 1;
            }
        }
    }

    printf("%d\n",res);



return 0;
}