Cod sursa(job #940456)

Utilizator rudarelLup Ionut rudarel Data 16 aprilie 2013 11:37:06
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <queue>
#define NMax 160
#define NNMax 25001
 
using namespace std;
 
 
struct Room{
    short x,y,val;
} room[NNMax];
 
queue<int> q , lst[NNMax];
bool viz[NMax * NMax];
short dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},ve[NMax][NMax];
 
int x,y,n,m,start,mini,minj,camera,curr,now,tot;
 
void lee(int xi,int yi){
    q.push(ve[xi][yi]);
    viz[start]=1;
 
    while(!q.empty())
    {
        now=q.front();
        while(!lst[now].empty())
        {
            curr=lst[now].front();
            if(viz[curr]==0){
                viz[curr]=1;
                q.push(curr);
            }
            lst[now].pop();
        }
 
        for(long i=0;i<4;i++){
            x=room[now].x+dx[i];
            y=room[now].y+dy[i];
            if((1<=x && x<=n) && (1<=y && y<=m) && !viz[ve[x][y]] )
                if(viz[room[ve[x][y]].val])
                    q.push(ve[x][y]),viz[ve[x][y]]=1;
                else
                    lst[room[ve[x][y]].val].push(ve[x][y]);
 
            }
 
        tot++;
        q.pop();
        }
}
 
int main()
{
    freopen("castel.in","rt",stdin);
    freopen("castel.out","wt",stdout);
 
    scanf("%ld %ld %ld",&n,&m,&start);
    for(long i=1;i<=n;i++){
        for(long j=1;j<=m;j++){
            scanf("%ld",&x);ve[i][j]=++camera;
            room[camera].x=i;room[camera].y=j;room[camera].val=x;
            if(camera==start) mini=i,minj=j;
        }
    }
 
    lee(mini,minj);
 
    printf("%ld\n",tot);
 
    return 0;
}