Cod sursa(job #1551156)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 15 decembrie 2015 11:13:57
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
#define MAXN 150
#define MAXM MAXN*MAXN
#define NRDIR 4
int dl[NRDIR]={-1, 0, 1, 0}, dc[NRDIR]={0, 1, 0, -1};
int a[MAXM+1], b[MAXM+1], next[MAXM+1], lista[MAXN+1][MAXN+1], l[MAXN*MAXN], c[MAXN*MAXN], viz[MAXN+2][MAXN+2], m;
inline void adauga(int x, int y, int l, int c){
    m++;
    a[m]=l;
    b[m]=c;
    next[m]=lista[x][y];
    lista[x][y]=m;
}
int main(){
    int ans, k, i, j, p, t, nrlin, nrcol, x, f;
    FILE *fin, *fout;
    fin=fopen("castel.in", "r");
    fout=fopen("castel.out", "w");
    fscanf(fin, "%d%d%d", &nrlin, &nrcol, &k);
    for(i=1; i<=nrlin; i++){
        for(j=1; j<=nrcol; j++){
            fscanf(fin, "%d", &x);
            adauga((x-1)/nrcol+1, (x-1)%nrcol+1, i, j);
        }
    }
    for(i=0; i<=nrlin+1; i++){
        viz[i][0]=viz[i][nrcol+1];
    }
    for(i=0; i<=nrcol+1; i++){
        viz[0][i]=viz[nrlin+1][i]=2;
    }
    f=1;
    l[0]=(k-1)/nrcol+1;
    c[0]=(k-1)%nrcol+1;
    viz[1][1]=2;
    ans=1;
    k=1;
    p=lista[1][1];
    while(p){
        if(viz[a[p]][b[p]]==0){
            viz[a[p]][b[p]]=1;
        }
        p=next[p];
    }
    while(f){
        t=k;
        f=0;
        for(i=0; i<t; i++){
            for(j=0; j<NRDIR; j++){
                if(viz[l[i]+dl[j]][c[i]+dc[j]]==1){
                    viz[l[i]+dl[j]][c[i]+dc[j]]=2;
                    ans++;
                    l[k]=l[i]+dl[j];
                    c[k]=c[i]+dc[j];
                    p=lista[l[k]][c[k]];
                    while(p){
                        if(viz[a[p]][b[p]]==0){
                            viz[a[p]][b[p]]=1;
                        }
                        p=next[p];
                    }
                    k++;
                    f=1;
                }
            }
        }
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}