Cod sursa(job #1660218)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 22 martie 2016 21:35:01
Problema Castel Scor 100
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[3*N*N];
int head,tail;

int xs,ys; //dimensiuni harta
int harta[N][N];

void vecini(int v[][2], int x,int y){
    int i;

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

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

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

struct pereche {
    int room,key;
}rk[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;
}

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,x2,y2,xn,yn;
    int i,j,temp;
    int rini, croom;
    int ix,key;
    int accesibile=0;
    int vhead[4][2], vnew[4][2];

    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;
        }
    }

    key=rk[rini].key;
    sort(rk,rk+ys*xs,cmp);

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

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

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

        vecini(vhead, x,y);

        //vecinii camerei curente
        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){//accesibila?
                key=x1+y1*xs;
                harta[y1][x1]=2;
                enq(key);

                ix=binsrch(key);//cauta camerele care se deschid cu noua cheie
                if(ix==-1){
                    continue;
                }

                while(rk[ix].key==key){
                    xn=(rk[ix].room)%xs;
                    yn=(rk[ix].room)/xs;
                    harta[yn][xn]=1;

                    //vecinii unei camere care a devenit accesibila cu noua cheie
                    vecini(vnew, xn, yn);
                    for(j=0;j<=3;j++){
                        if(vnew[j][0]==-1)
                            continue;
                        y2=vnew[j][1];
                        x2=vnew[j][0];

                        if(harta[y2][x2] == 2)
                            enq(x2+y2*xs);
                    }
                    ix++;
                }
            }
        }
    }

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