Pagini recente » Cod sursa (job #192504) | Cod sursa (job #542396) | Cod sursa (job #1607887) | Cod sursa (job #2571809) | Cod sursa (job #1660218)
#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;
}