Cod sursa(job #390044)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 2 februarie 2010 20:16:02
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<vector>
#include<bitset>

using namespace std;

int i,j,n,m,k,b[155][155],nr[155][155],rez;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

struct nod
{
	int x,y;
}p[50000];

vector <int> a[23000];
bitset <23000> cheie;
bitset <23000> pus;

void prelucreaza(int i,int j)
{
	int c=nr[i][j];
	cheie[c]=1;
	int l=a[c].size();
	if(l) 
		for(int t=l-1;t>=0;--t) 
		{
			p[++rez].x=a[c][t]/m+1;
			p[rez].y=a[c][t]%m;
			a[c].pop_back();
		}
		
	for(int t=0;t<4;++t)
	{
		int x1=i+dx[t];
		int y1=j+dy[t];
		
		if(x1>0&&x1<=n&&y1>0&&y1<=m&&!pus[nr[x1][y1]]) 
		{
			if(cheie[b[x1][y1]]) 
			{
				p[++rez].x=x1;
				p[rez].y=y1;
				pus[nr[x1][y1]]=1;
			}
			else 
			{
				c=b[x1][y1];
				a[c].push_back((x1-1)*m+y1);
				pus[nr[x1][y1]]=1;
			}
		}
	}
	
}
		
		
int main()
{
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	
	scanf("%d %d %d",&n,&m,&k);
	
	cheie[k]=1;
	pus[k]=1;
	int pas=0;
	
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			scanf("%d",&b[i][j]);
			nr[i][j]=++pas;
		}
		
	p[++rez].x=k/m+1;
    p[rez].y=k%m;
	
	for(i=1;i<=rez;++i) prelucreaza(p[i].x,p[i].y);
	
	printf("%d\n",rez);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}