Cod sursa(job #634955)

Utilizator Theorytheo .c Theory Data 18 noiembrie 2011 00:07:32
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.69 kb
#include<fstream>
#include<string>
#define nmax 55
using namespace std;
ifstream fin("valet.in");
ofstream fout("valet.out");
int i,j,n,m,L2,C2;
int a1[nmax][nmax],c1[120000][2],a2[nmax][nmax],a3[nmax][nmax],inca[nmax][nmax];
int ver[2501],ret;
int uz[5][2],r=0;
int ac[nmax][nmax];
int a4[nmax][nmax][200];
char c[nmax][nmax],v[nmax][nmax],a[nmax][nmax],v1[nmax][nmax],timp[nmax][nmax][200];
char aux;
int g=0;
int f;
int aju;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int ok=0;
long long dtot=0;
int x,y;
int m1,m2;
void citire();
void inti();
int lee();
void det2();
int det(int,int);
int det3();
int leeaux();
int lee2();
void rezolva();
int lee3();
void afis2();
int leef(int,int);
int timp1();
void citire()
{
	fin>>n>>m;
	
	for(i=1;i<=n;i++)
	{
		fin.get();
		fin.get(c[i],100,'\n');
		for(j=1;j<=m;j++)
		{
			a[i][j]=c[i][j-1];
			
		}
	}
	for(i=0;i<=n+1;i++)
	{
		a[i][0]='#';
		a[i][m+1]='#';
	}
	for(i=0;i<=m+1;i++)
	{
		a[0][i]='#';
		a[n+1][i]='#';
	}
	for(i=0;i<=n+1;i++)
	{
		for(j=0;j<=m+1;j++)
		{
			
			timp[i][j][0]=a[i][j];
			inca[i][j]=a[i][j];
			c[i][j]=a[i][j];
			v[i][j]=a[i][j];
			v1[i][j]=a[i][j];
			if(a[i][j]=='X')
			{
				L2=i;
				C2=j;
				timp[i][j][0]='c';
			}
			//fout<<c[i][j];
		}
		//fout<<'\n'; 
	}
	timp[1][1][0]='c';
}
void inti(int f)
{
	int i,j;
	for(i=0;i<=n+1;i++)
	{
		for(j=0;j<=m+1;j++)
		{
			timp[i][j][f]=timp[i][j][0];
			//fout<<timp[i][j][f];
			
		}
	//	fout<<'\n'; 
		
	}
}
int lee()
{
	int i,j,in,jn,p=1,d=1,k;
	c1[1][0]=L2;
	c1[1][1]=C2;
	c1[1][2]=1;
	c[L2][C2]='#';
	while(p<=d)
	{
		i=c1[p][0];
		j=c1[p][1];
		for(k=0;k<4;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
			if(c[in][jn]!='#')
			{
				d++;
				a1[in][jn]=a1[i][j]+1;
				c1[d][0]=in;
				c1[d][1]=jn;
				c1[d][2]=p;
				if(in==1&&jn==1)
					ret=a1[in][jn];
				//if(c[in][jn]='.')
					//ret=a1[in][jn];
				//ver[a1[in][jn]]++;
				c[in][jn]='#';
			}
		}
		p++;
	}
}
void det2()
{	
	int i,j,in,jn,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			ac[i][j]=a1[i][j];
}
int det(int x,int y)
{
	int i,j,in,jn,k;
	//a[x][y]=-1;
	i=x;
	j=y;
	for(k=0;k<4;k++)
	{
		in=i+dx[k];
		jn=j+dy[k];
		if(a1[in][jn]==a1[i][j]-1)
		{
			x=in;
			y=jn;
			//ver[a1[i][j]]++;
			a1[i][j]=-1;
			det(in,jn);
			break;
			
		}
	}
	//det(x,y);

	
}

int det3(int x,int y)
{
	int i,j,in,jn,k;
	//det2();
	//a[x][y]=-1;
	i=x;
	j=y;
	for(k=0;k<4;k++)
	{
		in=i+dx[k];
		jn=j+dy[k];
		if(ac[in][jn]==ac[i][j]-1&&in>0&&jn>0&&in<=n&&jn<=m&&timp[in][jn][0]!='#')
		{
			x=in;
			y=jn;
			//ver[a1[i][j]]++;
			ac[i][j]=-1;
			det3(in,jn);
			break;
			
		}
	}
	//det(x,y);

	
}
int leeaux()
{
	int i,j,in,jn,p=1,d=1,k;
	c1[1][0]=1;
	c1[1][1]=1;
	c1[1][2]=1;
	inca[1][1]='#';
	while(p<=d)
	{
		i=c1[p][0];
		j=c1[p][1];
		//a[i][j]='#';
		for(k=0;k<4;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
			if(inca[in][jn]!='#'&&(ac[in][jn]!=-1||ac[i][j]!=-1))
			{
				d++;
				//ver[a1[in][jn]]++;
				//a1[in][jn]=-1;
				c1[d][0]=in;
				c1[d][1]=jn;
				c1[d][2]=p;
				if(in==L2&&jn==C2)
				{
					//fout<<p<<'\n'; 
					return 1;
				}
				
				ac[in][jn]=-1;
				inca[in][jn]='#';
			}
		}
		p++;
	}
	return 0;
}
int lee2()
{
	int i,j,in,jn,p=1,d=1,k;
	c1[1][0]=1;
	c1[1][1]=1;
	c1[1][2]=1;
	a[1][1]='#';
	while(p<=d)
	{
		i=c1[p][0];
		j=c1[p][1];
		//a[i][j]='#';
		for(k=0;k<4;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
			if(a[in][jn]!='#'&&(a1[in][jn]!=-1||a1[i][j]!=-1))
			{
				d++;
				//ver[a1[in][jn]]++;
				//a1[in][jn]=-1;
				c1[d][0]=in;
				c1[d][1]=jn;
				c1[d][2]=p;
				if(in==L2&&jn==C2)
				{
					//fout<<p<<'\n'; 
					return 1;
				}
				
				//a1[i][j]=-1;
				a[in][jn]='#';
			}
		}
		p++;
	}
	return 0;
}
int afis()
{
	int i,j;
	/*
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			//fout<<a1[i][j]<<" ";
		}
		//fout<<'\n'; 
	}
	//fout<<ret;
		*/
}
void rezolva()
{
	int x;
	citire();
	lee();
	det2();
	det(1,1);
	
	x=lee2();
	afis();
	if(!x)
		fout<<"imposibil";
	else
	{
		lee3();
		timp1();
	}
	
}
int lee3()
{
	int i,j,in,jn,p=1,d=1,k;
	c1[1][0]=1;
	c1[1][1]=1;
	c1[1][2]=1;
	v1[1][1]='#';
	while(p<=d)
	{
		i=c1[p][0];
		j=c1[p][1];
		for(k=0;k<4;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
			if(v1[in][jn]!='#')
			{
				d++;
				a3[in][jn]=a3[i][j]+1;
				c1[d][0]=in;
				c1[d][1]=jn;
				c1[d][2]=p;
				if(in==L2&&jn==C2)
					ret=a3[in][jn];
				//if(c[in][jn]='.')
					//ret=a1[in][jn];
				//ver[a1[in][jn]]++;
				v1[in][jn]='#';
			}
		}
		p++;
	}
}
void afis2()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a3[i][j]==0)
				a3[i][j]=-1;
			//fout<<a3[i][j]<<" ";
		}
	//	fout<<'\n';
	}
	a3[1][1]=0;
			
}
int leef(int x,int y)
{
	int in,jn,i,j,k,p=1,d=1,q;
	c1[1][0]=x;
	c1[1][1]=y;
	c1[1][2]=1;
	while(p<=d)
	{
		i=c1[p][0];
		j=c1[p][1];
		for(k=0;k<4;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
			if(timp[in][jn][g]!='#')
			{
				a4[in][jn][g]=a4[i][j][g]+1;
				d++;
				c1[d][0]=in;
				c1[d][1]=jn;
				c1[d][2]=p;
			//	if(a3[in][jn]==ret&&in>0&&jn>0&&in<=n&&jn<=m&&ac[in][jn]==-1)
				{
					for(q=1;q<=r;q++)
					{
						if(in==uz[q][0]&&jn==uz[q][1])
						{
							dtot+=(a4[in][jn][g]+1);
							fout<<a4[in][jn][g]+1<<'\n';
							x=in;
							y=jn;
							return 0;
						}
					}
				}
				timp[in][jn][g]='#';
			}
		}
		p++;
		
	}
	
	
}
int timp1()
{
	int L1,C1,in,jn,i,j,k,k1,inn,jnn;
	//det2();
	det3(1,1);
	leeaux();
	/*
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			//if(!a3[i][j])
			//	a3[i][j]=-5;
			fout<<ac[i][j]<<" ";
		}
		fout<<'\n'; 
	}
	*/
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(!a3[i][j])
				a3[i][j]=-5;
		//	fout<<a3[i][j]<<" ";
		}
		//fout<<'\n'; 
	}
//	fout<<'\n';
	a3[1][1]=0;
	x=L2;
	y=C2;
	//fout<<a3[x][y]<<'\n';
	dtot=a3[x][y];
	ret--;
	while(ret)
	{
		g++;
		i=x;
		j=y;
		r=0;
		
		for(k=0;k<=3;k++)
		{
			in=i+dx[k];
			jn=j+dy[k];
		
			if(a3[in][jn]==a3[i][j]-1&&in>0&&jn>0&&in<=n&&jn<=m)
			{
				for(k1=0;k1<=3;k1++)
				{
					inn=in+dx[k1];
					jnn=jn+dy[k1];
		
					if(a3[inn][jnn]==a3[in][jn]-1)
					{
						r++;
						uz[r][0]=inn;
						uz[r][1]=jnn;
				
					}
				}
				
				
				timp[i][j][g]='.';
				
				inti(g);
				timp[in][jn][g]='#';
				x=in;
				y=jn;
				
						ret--;
				leef(i,j);
				
					break;
				
					
				
			}
				
		}
	}
	fout<<dtot;
}
int main()
{
	//det2();
	
	rezolva();
	//fout<<'\n'; 
	
	//lee3();
	//fout<<ret<<'\n'; 
	//afis2();
	//inti(1);
	//timp1();
	
	fin.close();
	fout.close();
	return 0;
}