Cod sursa(job #457360)

Utilizator bora_marianBora marian bora_marian Data 18 mai 2010 23:59:36
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<fstream>
using namespace std;
int v[22505],n,a[156][156],b[156][156],k,m,di[4]={-1,1,0,0},dj[4]={0,0,-1,1};
struct nod{
   int  pti,ptj;
   nod *next;};
nod *g[22505];
int vizitat[22505],cheie[22505],rez,istart,jstart;
void lee(int istart,int jstart);
ofstream fout("castel.out");
int main()
{
	ifstream fin("castel.in");
	fin>>n>>m>>k;
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			fin>>a[i][j];
	istart=k/m+1;
	jstart=k%m;
	lee(istart,jstart);
	//fout<<istart<<" "<<jstart;
	fout<<rez;
	/*for(i=1;i<=n;i++)
	{	
		for(j=1;j<=m;j++)
			fout<<b[i][j]<<" ";
		fout<<endl;
	}*/
	return 0;
}
void lee(int istart,int jstart)
{
	nod *st,*dr;
	cheie[a[istart][jstart]]=1;
	st=new nod;
	st->pti=istart;
	st->ptj=jstart;
	st->next=NULL;
	dr=st;
	rez++;
	b[istart][jstart]=1;
	while(st)
	{
		b[st->pti][st->ptj]=1;
		for(k=0;k<=3;k++)
		{
			int ii,jj;
			ii=st->pti+di[k];
			jj=st->ptj+dj[k];
	
			if(ii>=1 && ii<=n && jj>=1 && jj<=m)
			{	
				if(cheie[a[ii][jj]]==1 && b[ii][jj]==0)
				{
					b[ii][jj]=1;
					rez++;
					nod *t=new nod;
					t->pti=ii;
					t->ptj=jj;
					t->next=NULL;
					dr->next=t;
					dr=t;
					int ajut=(ii-1)*m+jj;
					cheie[ajut]=1;
				    for(nod *p=g[ajut];p;p=p->next)
						if(b[p->pti][p->ptj]==0)
						{
							nod *t=new nod;
							t->pti=p->pti;
					        t->ptj=p->ptj;
					        t->next=NULL;
					        dr->next=t;
					        dr=t;
						    int aj=(p->pti-1)*m+p->ptj;
						    cheie[aj]=1;
						    b[p->pti][p->ptj]=1;
							rez++;
				    }
						
				}
				if(cheie[a[ii][jj]]==0 && b[ii][jj]==0)
				{
					nod *t=new nod;
					t->pti=ii;
					t->ptj=jj;
					t->next=g[a[ii][jj]];
					g[a[ii][jj]]=t;
				}
			}	
		}
		nod *q=st;
		st=st->next;
		delete q;
	}
}