Cod sursa(job #1551135)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 15 decembrie 2015 10:47:35
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <cstdio>
#define MAXN 150
#define NRDIR 4
int dl[NRDIR]={-256, 0, 256, 0}, dc[NRDIR]={0, 1, 0, -1};
int m, dr, ans, urm[(MAXN<<8)+MAXN], last[(MAXN<<8)+MAXN];
int q[(MAXN<<8)+MAXN], t[(MAXN<<8)+MAXN], val[MAXN*MAXN+1], next[MAXN*MAXN+1], lista[(MAXN<<8)+MAXN], e[((MAXN+1)<<8)+MAXN+1], list[(MAXN<<8)+MAXN];
inline void adauga(int x, int y, int a, int b){
    m++;
    val[m]=(a<<8)+b;
    next[m]=lista[(x<<8)+y];
    lista[(x<<8)+y]=m;
}
int find(int x){
    if(x==t[x]){
        return x;
    }
    t[x]=find(t[x]);
    return t[x];
}
inline void unite(int x, int y){
    if(x==y){
        return ;
    }
    if(e[x]==2){
        int p=list[y];
        while(p){
            ans++;
            q[dr++]=p;
            p=urm[p];
        }
        t[y]=x;
    }else if(e[y]==2){
        int p=list[x];
        while(p){
            ans++;
            q[dr++]=p;
            p=urm[p];
        }
        t[x]=y;
    }else{
        t[x]=y;
        urm[last[y]]=list[x];
        last[y]=last[x];
    }
}
int main(){
    int nrlin, nrcol, k, i, j, x, l, c, st, p;
    FILE *fin, *fout;
    fin=fopen("castel.in", "r");
    fout=fopen("castel.out", "w");
    fscanf(fin, "%d%d%d", &nrlin, &nrcol, &k);
    for(i=0; i<nrlin; i++){
        for(j=0; j<nrcol; j++){
            fscanf(fin, "%d", &x);
            adauga((x-1)/nrcol, (x-1)%nrcol, i, j);
            t[(i<<8)+j]=(i<<8)+j;
            urm[(i<<8)+j]=0;
            list[(i<<8)+j]=(i<<8)+j;
            last[(i<<8)+j]=(i<<8)+j;
        }
    }
    l=(k-1)/nrcol;
    c=(k-1)%nrcol;
    e[(l<<8)+c]=2;
    st=0;
    dr=1;
    q[0]=(l<<8)+c;
    ans=1;
    while(st<dr){
        p=lista[q[st]];
        while(p){
            if(e[find(val[p])]==0){
                e[find(val[p])]=1;
                for(i=0; i<NRDIR; i++){
                    if((dl[i]/256+(val[p]>>8)>=0)&&(dl[i]/256+(val[p]>>8)<nrlin)&&(dc[i]+(val[p]&255)>=0)&&(dc[i]+(val[p]&255)<nrcol)&&(e[find(val[p]+dl[i]+dc[i])])){
                        unite(find(val[p]), find(val[p]+dl[i]+dc[i]));
                    }
                }
            }
            p=next[p];
        }
        st++;
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}