Cod sursa(job #1524570)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 14 noiembrie 2015 11:28:58
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#define N 151

using namespace std;

int q[N*N];
int head,tail;
int xs,ys;
int harta[N][N];
int vhead[4][2];

void vecini(int x,int y){
    int i;

    for(i=0;i<=3;i++){
        vhead[i][0]=vhead[i][1]=-1;
    }

    if(x-1>=0){
        vhead[0][0]=x-1;
        vhead[0][1]=y;
    }
    if(y-1>=0){
        vhead[1][0]=x;
        vhead[1][1]=y-1;
    }
    if(x+1<xs){
        vhead[2][0]=x+1;
        vhead[2][1]=y;
    }
    if(y+1<ys){
        vhead[3][0]=x;
        vhead[3][1]=y+1;
    }
}
int veciniverif(int x,int y){

    if(x-1>=0){
        if(harta[y][x-1]==2){
            return 1;
        }
    }
    if(y-1>=0){
        if(harta[y-1][x]==2){
            return 1;
        }

    }
    if(x+1<xs){
        if(harta[y][x+1]==2){
            return 1;
        }

    }
    if(y+1<ys){
        if(harta[y+1][x]==2){
            return 1;
        }

    }
    return 0;
}

struct pereche {
    int room,key;
}rk[N*N];

int kopen[N*N];

int binsrch(int nrk){
    int ls=0,ld=xs*ys,mid;

    while(ls<=ld){
        mid=(ls+ld)/2;
        if(nrk>rk[mid].key){
            ls=mid+1;
        }else if(nrk<rk[mid].key){
            ld=mid-1;
        }else if (nrk==rk[mid].key){
            while(rk[mid-1].key==nrk && mid-1>=0){
                mid--;
            }
            return mid;
        }
    }
    return -1;
}

void enq(int k){
    q[head++]=k;
}
int deq(){
    return q[tail++];
}

bool cmp(struct pereche a,struct pereche b){
    return a.key<b.key;
}

void printmap(){
    int i,j;

    for(i=0;i<ys;i++){
        for(j=0;j<xs;j++){
            printf("%d ",harta[i][j]);
        }
        printf("\n");
    }

}
int main(){
    int x,y,x1,y1,xn,yn;
    int rini,temp;
    int ix,key,i;
    int croom;
    int nr2=0;

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

    scanf("%d%d%d",&ys,&xs,&rini);
    rini--;

    for(y=0;y<ys;y++){
        for(x=0;x<xs;x++){
            scanf("%d",&temp);
            rk[y*xs+x].key=temp-1;
            rk[y*xs+x].room=y*xs+x;
            kopen[y*xs+x]=temp-1;
        }
    }

    sort(rk,rk+ys*xs,cmp);

    x=rini%xs;
    y=rini/xs;
    harta[y][x]=2;

    key=kopen[rini];
    ix=binsrch(key);

    while(rk[ix].key==key){
        x=(rk[ix].room)%xs;
        y=(rk[ix].room)/xs;
        harta[y][x]=1;
        ix++;
    }

    enq(rini);

    x=rini%xs;
    y=rini/xs;
    harta[y][x]=2;

    while(head-tail){
        croom=deq();
        x=croom%xs;
        y=croom/xs;

        vecini(x,y);
        for(i=0;i<4;i++){
            y1=vhead[i][1];
            x1=vhead[i][0];

            if(vhead[i][0]==-1){
                continue;
            }
            if(harta[y1][x1] ==1){
                key=x1+y1*xs;
                harta[y1][x1]=2;
                enq(key);

                ix=binsrch(key);
                if(ix==-1){
                    continue;
                }
                while(rk[ix].key==key){
                    xn=(rk[ix].room)%xs;
                    yn=(rk[ix].room)/xs;
                    harta[yn][xn]=1;
                    if(veciniverif(xn,yn)==1){
                        harta[yn][xn]=2;
                        enq(xn+yn*xs);
                    }
                    ix++;
                }
            }
        }
    }

    for(y=0;y<ys;y++){
        for(x=0;x<xs;x++){
            if(harta[y][x]==2){
                nr2++;
            }
        }
    }
    printf("%d",nr2);
    return 0;
}