Cod sursa(job #678445)

Utilizator RobertSSamoilescu Robert RobertS Data 11 februarie 2012 18:07:42
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

struct LLSI{
	int inf;
	LLSI *urm;
};
LLSI *v[22500],*c,*sf[22500];


struct LLDI{
	int inf;
	LLDI *urm, *prec;

};
LLDI *serie,*d, *sfserie,*e,*h;

int n,m,k,vizitat[22500];

void citire(){
f>>n>>m>>k;

for(int i=1;i<=n*m;i++){
v[i]= new LLSI;
v[i]->urm=NULL;
v[i]->inf =i;
sf[i]=v[i];

}

int nod;
for(int i=1;i<=n*m;i++){
f>>nod;
c=v[nod];
if(nod!= i)
while(c!=NULL){
c=new LLSI;
c->inf=i;
c->urm = NULL;
sf[nod]->urm =c;
sf[nod]=c;
break;
}
c=c->urm;
}

}




void formareserie(int x){
	serie = new LLDI;
	serie->urm =NULL;
	serie->prec = NULL;
	serie->inf=v[x]->inf;
	vizitat[serie->inf]=1;
	sfserie=serie;
	
	c=v[serie->inf]->urm;
	
	while(c!=NULL){
	if(c->inf==v[x]->inf+m || c->inf==v[x]->inf-m || c->inf==v[x]->inf-1 || c->inf==v[x]->inf+1)//// verificam daca sunt vecini
	{
	d=new LLDI;
	d->urm =NULL;
	d->inf=c->inf;
	vizitat[d->inf]=1;
	d->prec=sfserie;
	sfserie->urm=d;
	sfserie=d;
	}
	c=c->urm;
	
	}

	d=sfserie;
	while(d!=NULL){
			int ok=0;
		
		if(v[d->inf]->urm != NULL){
			c=v[d->inf]->urm;
			
			
			
			
			while(vizitat[c->inf]==1 && c->urm!=NULL)
				c=c->urm;
				
	
		h=serie;
	
	while(h!=NULL && !ok){
	if((h->inf==c->inf+m || h->inf==c->inf-m || h->inf==c->inf-1 || h->inf==c->inf+1) && vizitat[c->inf]==0){
	e=new LLDI;
	e->urm =NULL;
	e->inf=c->inf;
	e->prec=sfserie;
	sfserie->urm=e;
	sfserie=e;
	ok=1;
	vizitat[c->inf]=1;
	break;
	}
	h=h->urm;
	
	}
	
	
		}
		
	
	if(ok && c->urm==NULL)
		d=sfserie;
	else
	if(c->urm!=NULL){
		vizitat[c->inf]=1;
		c=c->urm;
		
	}
	
	else{
		d=d->prec;
	vizitat[c->inf]=1;
	}
	
	
}
}

int main(){
	citire();
	formareserie(k);
	int contor=0;
	
	d=serie;
	while(d!=NULL)
	{
	d=d->urm;
	}
	
	
	
	d=serie;
	while(d!=NULL){
	contor++;
	d=d->urm;
	}
	g<<contor;
	
	
	

return 0;
}