Pagini recente » Cod sursa (job #1052306) | Cod sursa (job #2473146) | Cod sursa (job #1763362) | Cod sursa (job #979528) | Cod sursa (job #1524570)
#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;
}