Cod sursa(job #721094)

Utilizator valiro21Valentin Rosca valiro21 Data 23 martie 2012 11:55:50
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <queue>
#define NMax 201

using namespace std;


struct Room{
	int x,y,val;
} room[NMax * NMax];

queue<int> q;
int ve[NMax][NMax],lst[NMax][10 * NMax];
bool viz[NMax * NMax];
int tot,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},now;
int x,y,n,m,start,mini,minj,camera;

void lee(int xi,int yi){
	q.push(ve[xi][yi]);
	viz[start]=1;

	while(!q.empty())
	{
		now=q.front();
		for(long i=1;i<=lst[now][0];i++)
		{
			if(viz[lst[now][i]]==0){
				viz[lst[now][i]]=1;
				q.push(lst[now][i]);
			}
		}
		lst[now][0]=0;

		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][++lst[room[ve[x][y]].val][0]]=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;
}